gplt天梯赛L2-2 发口罩详解_输入第一行是两个正整数 d 和 p(1≤d,p≤30),表示有 d 天的数据,市民两次获得口罩

28号那天参加了gplt天梯赛，第一次参加没啥经验，发挥得不是特别好吧。L2-2是我做的最后一题，确实卡了很久（写了半个多小时拿了1分，心疼自己）。昨天一天都在想这题，今天中午的时候终于被我写出来了，特地记录一下。

题目描述

为了抗击来势汹汹的 COVID19 新型冠状病毒，全国各地均启动了各项措施控制疫情发展，其中一个重要的环节是口罩的发放。

某市出于给市民发放口罩的需要，推出了一款小程序让市民填写信息，方便工作的开展。小程序收集了各种信息，包括市民的姓名、身份证、身体情况、提交时间等，但因为数据量太大，需要根据一定规则进行筛选和处理，请你编写程序，按照给定规则输出口罩的寄送名单。

输入格式

输入第一行是两个正整数 D 和 P（1≤D,P≤30），表示有 D 天的数据，市民两次获得口罩的时间至少需要间隔 P 天。

接下来 D 块数据，每块给出一天的申请信息。第 i 块数据（i=1,⋯,D）的第一行是两个整数 T
​i 和 S​i（1≤Ti, Si ≤1000），表示在第 i 天有 T​i条申请，总共有 S​i个口罩发放名额。随后 T​i行，每行给出一条申请信息，格式如下：
姓名 身份证号 身体情况 提交时间

给定数据约束如下：

• 姓名 是一个长度不超过 10 的不包含空格的非空字符串；
• 身份证号 是一个长度不超过 20 的非空字符串；
• 身体情况 是 0 或者 1，0 表示自觉良好，1 表示有相关症状；
• 提交时间 是 hh:mm，为24小时时间（由 00:00 到 23:59 例如09:08）。注意，给定的记录的提交时间不一定有序；
• 身份证号各不相同，同一个身份证号被认为是同一个人，数据保证同一个身份证号姓名是相同的。

能发放口罩的记录要求如下：

• 身份证号 必须是 18 位的数字（可以包含前导0）；
• 同一个身份证号若在第 i 天申请成功，则接下来的 P 天不能再次申请。也就是说，若第 i 天申请成功，则等到第 i+P+1 天才能再次申请；
• 在上面两条都符合的情况下，按照提交时间的先后顺序发放，直至全部记录处理完毕或 S​i个名额用完。如果提交时间相同，则按照在列表中出现的先后顺序决定。

输出格式

对于每一天的申请记录，每行输出一位得到口罩的人的姓名及身份证号，用一个空格隔开。顺序按照发放顺序确定。

在输出完发放记录后，你还需要输出有合法记录的、身体状况为 1 的申请人的姓名及身份证号，用空格隔开。顺序按照申请记录中出现的顺序确定，同一个人只需要输出一次。

输入样例

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
9
10
11
12
13
14
15
16

输出样例

D 123456789012345672
A 123456789012345670
B 123456789012345671
E 123456789012345674
C 123456789012345673
A 123456789012345670
A 123456789012345670
E 123456789012345674
1
2
3
4
5
6
7
8

输出中，第一行到第三行是第一天的部分；第四、五行是第二天的部分；第三天没有符合要求的市民；第六行是第四天的部分。最后两行按照出现顺序输出了可能存在身体不适的人员。

思路讲解

这样的模拟题做起来还是挺怕的，细节很多。先分析一下题目要求：

1. 列出每天获得口罩的人的姓名和身份证号码
2. 只有身份证长度为18且全数字才为一个合法的身份证号码
3. 每天输出获得口罩的人必须按一定顺序进行排序
4. 每天口罩量是限额的（这一点在第3点的限制下会出现不一样的情况，先排序和后排序是两个结果）
5. 最后输出合法身份证申请时状态为1的记录（按申请顺序排序，不重复）

我从外层循环开始将程序分为三部分：

1. 输入记录、排除不合法身份证的记录、更新合法身份证申请时状态为1的记录
2. 排序
3. 筛选符合条件的记录

变量定义

vector<pair<string, string>> stList, ans;
map<string, int> records;
vector<Person> list;
int d, p, t, s;
1
2
3
4

• stList：保存合法身份证申请时状态为1的记录
• ans：保存这一天的获得口罩的申请记录
• records：获得口罩的冷却记录
• d、p、t、s: 见题

这里有一个类Person，定义如下：

class Person {
	string name, ID;
	int state;
	int subTime, subId; 
	
	public:
		bool input(istream& in, int id);
		bool isState();
		string& getID();
		string& getName();
		int getSubTime();
		int getSubId(); 
};
1
2
3
4
5
6
7
8
9
10
11
12
13

变量

• name: 名字
• ID: 身份证号码
• state: 状态（0、1）
• subTime: 提交时间
• subId: 提交编号（顺序）

方法

• input: 读取输入，对所有成员变量赋值，当身份证合法时返回true，否则false。in是输入流，id输入编号
• isState: 返回state的值
• getID: 返回ID的引用
• getName: 返回name的引用
• getSubTime: 获取提交时间
• getSubId: 获取提交编号

输入

对于题目要求的d和p在程序一开始输入

cin >> d >> p;
1

然后在一个0 ~ (d - 1)的循环开头读取t和s

for (int i = 0; i < d; i++) {
	cin >> t >> s;
	....
}
1
2
3
4

在一个0 ~ (t - 1)的内层循环开头读取记录

for (int j = 0; j < t; j++) {
	Person person;
	if (!person.input(cin, j)) continue;
	....
}
1
2
3
4
5

因为input读取的ID是不合法的时候返回false所以在这里就可以过滤不合法身份证的记录
最后大体输入结构应该是这样的

cin >> d >> p;
for (int i = 0; i < d; i++) {
	cin >> t >> s；
	....
	for (int j = 0; j < t; j++) {
		Person person;
		if (!person.input(cin, j)) continue;
		....
	}
	....
}
1
2
3
4
5
6
7
8
9
10
11

第一部分

输入记录、排除不合法身份证的记录这两点已在输入部分给出
更新合法身份证申请时状态为1的记录的代码如下：

if (person.isState()) {
	bool flag = true; 
	for (pair<string, string> e : stList) {
		if (e.first == person.getID()) {
			flag = false;
			break;
		}
	} 
	if (flag) stList.push_back({person.getID(), person.getName()});
}
1
2
3
4
5
6
7
8
9
10

只处理状态为1的记录，定义一个初始为true的flag标志，遍历stList的记录，这个ID有出现过则将flag置false并跳出遍历，最后判断标志位，若为true则把这条记录添加到stList（只取id和name，因为只需要按输入顺序排序所以不需要特殊处理）。
最后代码如下：

for (int j = 0; j < t; j++) {
	Person person;
	if (!person.input(cin, j)) continue;
	//合法的输入
	//状态1 
	if (person.isState()) {
		bool flag = true; 
		for (pair<string, string> e : stList) {
			if (e.first == person.getID()) {
				flag = false;
				break;
			}
		} 
		if (flag) stList.push_back({person.getID(), person.getName()});
	}
	//放入list
	list.emplace_back(person); 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

第二部分

没啥可讲的

sort(list.begin(), list.end(), comp);
1

comp实现如下

bool comp(Person& a, Person& b) {
	if (a.getSubTime() != b.getSubTime()) return a.getSubTime() < b.getSubTime();
	return a.getSubId() < b.getSubId();
}
1
2
3
4

第三部分

筛选符合条件的记录
一个循环遍历搞定，先贴代码：

for (Person& pe : list) {
	if (!s) break;
	if (records[pe.getID()] <= i) {
		records[pe.getID()] = i + p + 1;
		ans.push_back({pe.getID(), pe.getName()});
		s--;
	} 
}
1
2
3
4
5
6
7
8

先判断s是否为0，是就跳出循环，因为map中一开始是空的，并且map在访问一个不存在的键时会创建一个默认的值放入，int默认为0，所以直接拿来比就行了，第一次加入的数据永远<=i。到了if语句块，就更新值为i + p + 1，即下一个冷却到期的日子，再把其记录到ans中，最后s–。

输出

一个在外层循环的每日领取记录的输出

for (auto& e : ans) cout << e.second << ' ' << e.first << endl;
1

一个在程序结尾处的合法身份证申请时状态为1的记录的输出

for (auto& e : stList) cout << e.second << ' ' << e.first << endl;
1

所以输出结构大概是这样的：

....
for (int i = 0; i < d; i++) {
	....
	for (auto& e : ans) cout << e.second << ' ' << e.first << endl;
} 
for (auto& e : stList) cout << e.second << ' ' << e.first << endl;

return 0;
1
2
3
4
5
6
7
8

代码实现

#include <bits/stdc++.h>

using namespace std;

class Person {
	string name, ID;
	int state;
	int subTime, subId; 
	
	public:
		bool input(istream& in, int id);
		bool isState();
		string& getID();
		string& getName();
		int getSubTime();
		int getSubId(); 
};

bool Person::input(istream& in, int id) {
	int h;
	in >> this->name >> this->ID >> this->state >> h;
	in.ignore();
	in >> this->subTime;
	this->subTime += h * 60;
	this->subId = id;
	
	if (this->ID.size() != 18) return false;
	for (int i = 0; i < 18; i++) {
		if (!isdigit(this->ID[i])) return false;
	}
	return true;
}

bool Person::isState() {
	return this->state == 1;
}

string& Person::getID() {
	return this->ID;
}

string& Person::getName() {
	return this->name;
}

int Person::getSubTime() {
	return this->subTime;
}

int Person::getSubId() {
	return this->subId;
}

bool comp(Person& a, Person& b) {
	if (a.getSubTime() != b.getSubTime()) return a.getSubTime() < b.getSubTime();
	return a.getSubId() < b.getSubId();
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	vector<pair<string, string>> stList, ans;
	map<string, int> records;
	vector<Person> list;
	int d, p, t, s;
	
	cin >> d >> p;
	
	for (int i = 0; i < d; i++) {
		cin >> t >> s;
		
		list.clear();
		ans.clear();
		
		for (int j = 0; j < t; j++) {
			Person person;
			if (!person.input(cin, j)) continue;
			//合法的输入
			//状态1 
			if (person.isState()) {
				bool flag = true; 
				for (pair<string, string> e : stList) {
					if (e.first == person.getID()) {
						flag = false;
						break;
					}
				} 
				if (flag) stList.push_back({person.getID(), person.getName()});
			}
			//放入list
			list.emplace_back(person); 
		}
		//排序
		sort(list.begin(), list.end(), comp);
		//筛选
		for (Person& pe : list) {
			if (!s) break;
			if (records[pe.getID()] <= i) {
				records[pe.getID()] = i + p + 1;
				ans.push_back({pe.getID(), pe.getName()});
				s--;
			} 
		}
		//输出本日发放记录
		for (auto& e : ans) cout << e.second << ' ' << e.first << endl;
	} 
	//输出state == 1的
	for (auto& e : stList) cout << e.second << ' ' << e.first << endl;
	
	return 0;
} 
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113