背景 一道阴间模拟题,有很多小细节需要注意,之前被小细节卡了很久,在网上也找不到这方面的一个说明。因此博客记录一下,希望能给其他被卡住的人一点启发。
题目描述 为了抗击来势汹汹的 COVID-19 新型冠状病毒,全国各地均启动了各项措施控制疫情发展,其中一个重要的环节是口罩的发放。
某市出于给市民发放口罩的需要,推出了一款小程序让市民填写信息,方便工作的开展。小程序收集了各种信息,包括市民的姓名、身份证、身体情况、提交时间等,但因为数据量太大,需要根据一定规则进行筛选和处理,请你编写程序,按照给定规则输出口罩的寄送名单。
输入格式 输入第一行是两个正整数 $D$ 和 $P$($1 \leq D,P \leq 30$),表示有 $D$ 天的数据,市民两次获得口罩的时间至少需要间隔 $P$ 天。
接下来 $D$ 块数据,每块给出一天的申请信息。第 $i$ 块数据($i=1,⋯,D$)的第一行是两个整数 $Ti$ 和 $Si$($1 \leq Ti,Si \leq 1000$),表示在第 $i$ 天有 $Ti$ 条申请,总共有 $Si$ 个口罩发放名额。随后 $Ti$ 行,每行给出一条申请信息,格式如下:
给定数据约束如下:
姓名
是一个长度不超过 $10$ 的不包含空格的非空字符串;
身份证号
是一个长度不超过 $20$ 的非空字符串;
身体情况
是 $0$ 或者 $1$,$0$ 表示自觉良好,$1$ 表示有相关症状;
提交时间
是 $hh:mm$,为24小时时间(由 00:00
到 23:59
。例如 $09:08$)。注意,给定的记录的提交时间不一定有序;
身份证号
各不相同,同一个身份证号被认为是同一个人,数据保证同一个身份证号姓名是相同的。
能发放口罩的记录要求如下:
身份证号
必须是 $18$ 位的数字(可以包含前导$0$);
同一个身份证号若在第 $i$ 天申请成功,则接下来的 $P$ 天不能再次申请。也就是说,若第 $i$ 天申请成功,则等到第 $i+P+1$ 天才能再次申请;
在上面两条都符合的情况下,按照提交时间的先后顺序发放,直至全部记录处理完毕或 $Si$ 个名额用完。如果提交时间相同,则按照在列表中出现的先后顺序决定。
输出格式 对于每一天的申请记录,每行输出一位得到口罩的人的姓名及身份证号,用一个空格隔开。顺序按照发放顺序确定。
在输出完发放记录后,你还需要输出有合法记录的、身体状况为 1 的申请人的姓名及身份证号,用空格隔开。顺序按照申请记录中出现的顺序确定,同一个人只需要输出一次。
输入样例 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 4 2 5 3 A 123456789012345670 1 13:58 B 123456789012345671 0 13:58 C 12345678901234567 0 13:22 D 123456789012345672 0 03:24 C 123456789012345673 0 13:59 4 3 A 123456789012345670 1 13:58 E 123456789012345674 0 13:59 C 123456789012345673 0 13:59 F F 0 14:00 1 3 E 123456789012345674 1 13:58 1 1 A 123456789012345670 0 14:11
输出样例 1 2 3 4 5 6 7 8 D 123456789012345672 A 123456789012345670 B 123456789012345671 E 123456789012345674 C 123456789012345673 A 123456789012345670 A 123456789012345670 E 123456789012345674
样例解释 输出中,第一行到第三行是第一天的部分;第四、五行是第二天的部分;第三天没有符合要求的市民;第六行是第四天的部分。最后两行按照出现顺序输出了可能存在身体不适的人员。
思路 这是一道典型的模拟,需要思考如何简洁处理好这些细节。
我考虑的是由于身份证号唯一,因此可以使用$map$这样一种结构,把对应的身份证号码映射到具体的人。
然后,题目要求求当日申请成功的人和疑似不适的人两种。
因此:
使用$ vector< string > \ canID $来存放当日不适的人。
使用$ vector< string > \ susID $来存放所有合法的提交中,疑似不适的人。
这样使用 $ vector $ 来存放,能够满足满足按照列表出现顺序排的要求。需要统计某元素是否有出现过可以使用 $ count(start, end, val) $ 。
然后考虑时间排序问题,由于给定的是指定的$hh:mm$的格式的时间,因此可以直接对指定位置的字符串提取时间,然后记录下来再$sort$。
也可以使用$cin >> h >> ch >> m$这样的方式进行读入,相当于$C$语言中$scanf$的%d%c%d
,快速获得时间。
最后,考虑一个$P$天内不能申请的问题。因为前面我使用$map$将身份证号映射到具体的人,于是我可以直接修改这个人的属性,来标记最近一次申请是什么时候。如果从来没有申请过,则初始值置为$-INF$ 。
坑点 按照上面的思路写代码还是很快的,但是事实上容易遇到不少坑点。
坑点1 1 2 3 4 5 6 7 8 9 10 11 12 13 for (int i = 0 ; i < vday.size (); i++){ if (mp[vday[i].ID].las + P + 1 <= nD) { canID.push_back(vday[i].ID); mp[vday[i].ID].las = nD; Si--; } if (Si == 0 ) break ; }
坑点2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 for (int i = 1 ; i <= Ti; i++){ int tsta; string tname, tID, tstime; cin >> tname >> tID >> tsta >> tstime; if (!checkID(tID)) continue ; if (!mp.count(tID)) mp[tID] = (Citizen){tname, tID, tstime, tsta, -INF, 0 }; vday.push_back(mp[tID]); if (tsta == 1 && !count(susID.begin (), susID.end (), tID)) susID.push_back(tID); }
坑点3 1 2 3 4 5 6 7 8 9 10 11 12 13 for (int i = 0 ; i < vday.size (); i++){ if (Si == 0 ) break ; if (vday[i].las + P + 1 <= nD) { canID.push_back(vday[i].ID); mp[vday[i].ID].las = nD; Si--; } }
坑点4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 bool operator < (const Citizen &A, const Citizen &B){ int ah = (A.stime[0 ] - '0' ) * 10 + (A.stime[1 ] - '0' ); int am = (A.stime[3 ] - '0' ) * 10 + (A.stime[4 ] - '0' ); int bh = (B.stime[0 ] - '0' ) * 10 + (B.stime[1 ] - '0' ); int bm = (B.stime[3 ] - '0' ) * 10 + (B.stime[4 ] - '0' ); if (ah == bh) { if (am == bm) return A.ct < B.ct; return am < bm; } return ah < bh; } sort(vday.begin (), vday.end ());
完整AC代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 #include <bits/stdc++.h> #define maxn 100005 #define INF (1 << 30) using namespace std ;int D, P, Ti, Si;struct Citizen { string name; string ID; string stime; int status; int las; int ct; }; bool operator < (const Citizen &A, const Citizen &B){ int ah = (A.stime[0 ] - '0' ) * 10 + (A.stime[1 ] - '0' ); int am = (A.stime[3 ] - '0' ) * 10 + (A.stime[4 ] - '0' ); int bh = (B.stime[0 ] - '0' ) * 10 + (B.stime[1 ] - '0' ); int bm = (B.stime[3 ] - '0' ) * 10 + (B.stime[4 ] - '0' ); if (ah == bh) { if (am == bm) return A.ct < B.ct; return am < bm; } return ah < bh; } vector <string > susID;map <string , Citizen> mp;bool checkID (string str) { int len = str.length(); if (len != 18 ) return false ; for (int i = 0 ; i <= len - 1 ; i++) if (str[i] < '0' || str[i] > '9' ) return false ; return true ; } int main (void ) { scanf ("%d %d" , &D, &P); for (int nD = 1 ; nD <= D; nD++) { scanf ("%d %d" , &Ti, &Si); vector <Citizen> vday; vector <string > canID; for (int i = 1 ; i <= Ti; i++) { int tsta; string tname, tID, tstime; cin >> tname >> tID >> tsta >> tstime; if (!checkID(tID)) continue ; if (!mp.count(tID)) mp[tID] = (Citizen){tname, tID, tstime, tsta, -INF, 0 }; mp[tID].ct = i; mp[tID].status = tsta; mp[tID].stime = tstime; vday.push_back(mp[tID]); if (tsta == 1 && !count(susID.begin (), susID.end (), tID)) susID.push_back(tID); } sort(vday.begin (), vday.end ()); for (int i = 0 ; i < vday.size (); i++) { if (Si == 0 ) break ; if (mp[vday[i].ID].las + P + 1 <= nD) { canID.push_back(vday[i].ID); mp[vday[i].ID].las = nD; Si--; } } for (int i = 0 ; i < canID.size (); i++) cout << mp[canID[i]].name << ' ' << canID[i] << '\n' ; } for (int i = 0 ; i < susID.size (); i++) cout << mp[susID[i]].name << ' ' << susID[i] << '\n' ; return 0 ; }
别的 还记得去年$CCCC$这道题过样例了一交,然后…拿了一分还是零分…
麻了…
希望今年不要白给,拿到个个人奖…