L2-034 口罩发放

背景

一道阴间模拟题,有很多小细节需要注意,之前被小细节卡了很久,在网上也找不到这方面的一个说明。因此博客记录一下,希望能给其他被卡住的人一点启发。

题目描述

为了抗击来势汹汹的 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$ 行,每行给出一条申请信息,格式如下:

1
姓名 身份证号 身体情况 提交时间

给定数据约束如下:

  • 姓名 是一个长度不超过 $10$ 的不包含空格的非空字符串;
  • 身份证号 是一个长度不超过 $20$ 的非空字符串;
  • 身体情况 是 $0$ 或者 $1$,$0$ 表示自觉良好,$1$ 表示有相关症状;
  • 提交时间 是 $hh:mm$,为24小时时间(由 00:0023: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<string, Citizen>$这样一种结构,把对应的身份证号码映射到具体的人。

然后,题目要求求当日申请成功的人和疑似不适的人两种。

因此:

使用$ 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
//vday存放的是今日的合法申请。
//这种写法会被当日口罩配额为0的数据HACK掉
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;
//HACK 1, Si == 0 放到 if(vday[i].las + P ....) 后
}

坑点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
//每一次读入Ti个人的信息时
for(int i = 1; i <= Ti; i++)
{
int tsta;
string tname, tID, tstime;
cin >> tname >> tID >> tsta >> tstime;
//cout << "debug: " << tname << " " << tID << " " << tsta << " " << tstime << '\n';
if(!checkID(tID)) continue;
//如果从未出现,则利用刚读入的信息初始化掉
if(!mp.count(tID))
mp[tID] = (Citizen){tname, tID, tstime, tsta, -INF, 0};
//而我没有考虑对于已经出现过的数据,像提交时间这样的数据是会变化的
//因此要在这里进行修改
//HACK 2, mp[tID]其他权值没有更新

//这段注释掉的代码是新增用于解决这个问题的
/*
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);
}

坑点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;
//HACK 3, 这里写的是vday[i].las, 而不是mp[vday[i].ID].las
//这不能处理一个人在一天内连续申请(WA 5)的情况
//因为我使用的更新方法是直接更新mp[ID]映射到的具体的人,而不是存下来的当前的合法申请人的信息
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;
}
//HACK 4, 直接sort需要记录出现次序,判断先输出哪一个,否则会因为sort的不稳定性出现错误
//实测如果不记录出现次序,用stable_sort也是可以的
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)
{
//freopen("input.txt", "r", stdin);
//freopen("debug.txt", "w", stdout);
scanf("%d %d", &D, &P);
for(int nD = 1; nD <= D; nD++)
{
scanf("%d %d", &Ti, &Si);
//printf("DEBUG: %d %d %d\n", nD, 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;
//cout << "debug: " << tname << " " << tID << " " << tsta << " " << tstime << '\n';
if(!checkID(tID)) continue;
if(!mp.count(tID))
mp[tID] = (Citizen){tname, tID, tstime, tsta, -INF, 0};
//HACK 2, mp[tID]其他权值没有更新
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);
}
//if(vday.size() == 0 || Si == 0) continue;

//HACK 4, 直接sort需要记录出现次序,判断先输出哪一个
sort(vday.begin(), vday.end());
for(int i = 0; i < vday.size(); i++)
{
//HACK 1, Si == 0 放到 if(vday[i].las + P ....) 后
if(Si == 0) break;
//HACK 3, 原来我这里写的是vday[i].las, 而不是mp[vday[i].ID].las
//这不能处理一个人在一天内连续申请(WA 5)
if(mp[vday[i].ID].las + P + 1 <= nD)
{
canID.push_back(vday[i].ID);
mp[vday[i].ID].las = nD;
Si--;
}
}
//cout << "DEBUG: " << canID.size() << endl;
//printf("+++\n");
for(int i = 0; i < canID.size(); i++)
cout << mp[canID[i]].name << ' ' << canID[i] << '\n';
//printf("+++\n");
}
for(int i = 0; i < susID.size(); i++)
cout << mp[susID[i]].name << ' ' << susID[i] << '\n';
return 0;
}

别的

还记得去年$CCCC$这道题过样例了一交,然后…拿了一分还是零分…

麻了…

希望今年不要白给,拿到个个人奖…