背景

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

题目描述

为了抗击来势汹汹的 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: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
//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$这道题过样例了一交，然后…拿了一分还是零分…

麻了…

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