GPLT团体程序设计天梯赛分类练习2：排序+栈+队列

摘要

L2-3 名人堂与代金券 - 团体程序设计天梯赛练习2：排序+栈+队列

L2-2 冰岛人 - 团体程序设计天梯赛练习2：排序+栈+队列

L2-1 简单计算器 - 团体程序设计天梯赛练习2：排序+栈+队列

7-4 口罩发放 - 团体程序设计天梯赛练习2：排序+栈+队列

7-5 包装机 - 团体程序设计天梯赛练习2：排序+栈+队列

7-6 清点代码库 - 团体程序设计天梯赛练习2：排序+栈+队列

7-7 插松枝 - 团体程序设计天梯赛练习2：排序+栈+队列

7-8 老板的作息表 - 团体程序设计天梯赛练习2：排序+栈+队列

L2-3 名人堂与代金券

题解

有N个人的邮箱 和 成绩，前K名可以进入名人堂。

总评分在 [G, 100] 区间内者，可以得到 50 元 PAT 代金券；在 [60, G) 区间内者，可以得到 20 元PAT代金券。

求奖金总数 和 进入名人堂的名单。

代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;

// 先按分数排序，再按名称排序
// first try：20min
struct stu{
	string name;
	int sco,rk;
	bool operator<(const stu & rhs){
		if(sco != rhs.sco) return sco > rhs.sco;
		return name < rhs.name;
	}
}s[maxn];

int n,g,k,sum;

int main(void){
	cin>>n>>g>>k;
	for(int i = 1 ; i <= n ; i ++){
		cin>>s[i].name>>s[i].sco;
		if(s[i].sco >= g && s[i].sco <= 100) sum += 50;
		if(s[i].sco >= 60 && s[i].sco < g) sum += 20;
	}
	cout<<sum<<"\n";
	sort(s+1,s+1+n);
	// 求每个学生的rank
	for(int i = 1; i <= n; i ++){
		if((i == 1) || (s[i].sco < s[i-1].sco)) s[i].rk = i;
		else s[i].rk = s[i-1].rk;
	}
	int t = 1;
	while(t <= n && s[t].rk <= k){
		cout<<s[t].rk<<" "<<s[t].name<<" "<<s[t].sco<<"\n";
		t++;
	}
	return 0;
}

L2-2 冰岛人

题解

根据冰岛人的姓，可以判断其 性别 和 父亲。

题目要求我们：

1）判断2人的性别相同/不同

2）判断2人是否五代之内有相同祖先。

用哈希表存储性别，进行判断1）；然后，根据每个人的父亲，构造一张谱系树图，进行判断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
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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5;

int n,m,cnt;
unordered_map<string, string> pre;
unordered_map<string, bool> g;
set<string > v;

// 我，父亲，爷爷，曾祖父
// 1 2 3 4
bool judge(string q1, string q2){
	for(int i = 1 ; i <= 4 ; i ++){
		string temp = q2;
		while(true){
			if(q2 == q1) return false;
			if(!pre.count(q2)) break;
			else q2 = pre[q2];
		}
		if(!pre.count(q1)) break;
		q1 = pre[q1];
		q2 = temp;
	}
	return true;
}

string solve(){
	string q1,q2,str;
	cin>>q1>>str>>q2>>str;
	if(!v.count(q1) || !v.count(q2)) return "NA";
	if(g[q1] == g[q2]) return "Whatever";
	if(judge(q1,q2) && judge(q2,q1)) return "Yes";
	return "No";
}

int main(void){
	cin>>n;
	// 坑点：一个人若不是维京人{-m, -f}；
	// 他自己需要被算在谱系里，但他的父亲不能被算在谱系里。
	for(int i = 1 ; i <= n ; i ++){
		string s1,s2; cin>>s1>>s2;
		v.insert(s1);
		if(s2.back() == 'm'){
			g[s1] = true;
		}else if(s2.back() == 'f'){
			g[s1] = false;
		}else if(s2.back() == 'n'){
			g[s1] = true;
			pre[s1] = s2.substr(0,s2.length() - 4);
		}else if(s2.back() == 'r'){
			g[s1] = false;
			pre[s1] = s2.substr(0,s2.length() - 7);
		}
	}
	cin>>m;
	while(m--){
		cout<<solve()<<"\n";
	}
	return 0;
}

L2-1 简单计算器

题解

题目要求我们构造2个栈，1个用来存储数字，1个用来存储运算符。

每次从栈1中取出2个数字，栈2中取出一个运算符，将结果存入栈1。

进行模拟，直到栈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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;

stack<int > s1;
stack<char> s2;
int n;

int cal(int a, int b, char op){
	if(op == '-') return a-b;
	if(op == '+') return a+b;
	if(op == '*') return a*b;
	if(op == '/'){
		if(b == 0){
			cout<<"ERROR: "<<a<<"/"<<b<<"\n";
			exit(0);
		}
		return a/b;
	}
	return -1;
}


int main(void){
	cin>>n;
	for(int i = 1 ; i <= n ; i ++){
		int t;cin>>t;
		s1.push(t);
	}
	for(int i = 1 ; i <= n-1 ; i ++){
		char c;cin>>c;
		s2.push(c);
	}
	while(!s2.empty()){
		int n1 = s1.top();s1.pop();
		int n2 = s1.top();s1.pop();
		char op = s2.top();s2.pop();
		s1.push(cal(n2,n1,op));
	}
	cout<<s1.top();
	return 0;
}

7-4 口罩发放

题解

题目的任务包括2个：

1）对于每天的申请列表，按题目给定顺序，输出合法的申请，即 满足 A.身份证合法 B.间隔超过P天 的申请

2）按题目给定顺序，输出每个身体状况为1的病人名单。

注意：1）和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
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
#include<bits/stdc++.h>
using namespace std;

struct record{
	string name,card,mm;
	int sta,tim,idx;
	bool operator<(const record & rhs){
		if(tim != rhs.tim) return tim < rhs.tim;
		return idx < rhs.idx;
	}
};

struct person{
	string name,card;
};

int d,p;
unordered_map<string, int> lastDay;
vector<person> sick;

// 身份证判断
bool judge_card(string card){
	if(card.length() != 18) return false;
	for(int i = 0 ; i < 18 ; i ++){
		if(!(card[i] >= '0' && card[i] <= '9')) return false;
	}
	return true;
}

// 时间转换
int get_time(string s){
	int h = (s[0] - '0')*10 + (s[1] - '0');
	int m = (s[3] - '0')*10 + (s[4] - '0');
	return 60*h + m;
}

void print_sick(){
	for(auto it : sick){
		cout<<it.name<<" "<<it.card<<"\n";
	}
}

void solve(int day){
	int t,s; cin>>t>>s;
	vector<record> v;
	for(int i = 1 ; i <= t ; i ++){
		record r;
		cin>>r.name>>r.card>>r.sta>>r.mm;
		r.idx = i;
		r.tim = get_time(r.mm);
		v.push_back(r);
		// 统计病人【排序：列表顺序】
		if(judge_card(r.card) && r.sta == 1){
			bool vis = false;
			for(auto it : sick){
				if(it.card == r.card){
					vis = true;
					break;
				}
			}
			if(!vis) sick.push_back({r.name, r.card});
		}
	}
	// 输出当天领取口罩列表【排序：出现时间 > 列表顺序】
	sort(v.begin(),v.end());
	for(auto it : v){
		if(judge_card(it.card)){
			if(s > 0 && (!lastDay.count(it.card) || day - lastDay[it.card] > p)){
				cout<<it.name<<" "<<it.card<<endl;
				lastDay[it.card] = day;
				s--;
			}
		}
	}
}

int main(void){
	cin>>d>>p;
	for(int i = 1 ; i <= d ; i ++){
		solve(i);
	}
	print_sick();
	return 0;
}

7-5 包装机

题解

题目给定了N个运输带，每个运输带上有M个物品，用字符表示，栈内最多存L个物品。

每次按下按钮，若按钮为0，从栈内取出1个物品；若按钮为其他数字，从该下标的运输带上取下物品，放入栈中。

栈内最多存放L个物品，若超过，先取出1个。

输出栈内取出的物品顺序。

代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;

int n,m,l;
stack<char> s;
queue<char> q[maxn];

int main(void){
	cin>>n>>m>>l;
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			char t; cin>>t;
			q[i].push(t);
		}
	}
	int op;
	while(cin>>op, op != -1){
		if(op == 0){
			if(!s.empty()){
				cout<<s.top(); s.pop();
			}
		}else{
			if(!q[op].empty()){
				if(s.size() >= l){
					cout<<s.top(); s.pop();
				}
				s.push(q[op].front());
				q[op].pop();
			}
		}
	}
	return 0;
}

7-6 清点代码库

题解

给定 N个 数组，每个数组包含M个整数。

我们需要求N个数组中的重复项，并按 重复数 > 数组大小 的规则输出。

注意：这里的数组大小不是长度，指的是vector的排序规则。

代码

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
#include<bits/stdc++.h>
using namespace std;

struct record{
	int cnt;
	vector<int > v;
	bool operator<(const record & rhs){
		if(cnt != rhs.cnt) return cnt > rhs.cnt;
		return v < rhs.v;
	}
};

map<vector<int>, int> mp;
vector<record> ans;
int n,m,idx;

int main(void){
	cin>>n>>m;
	for(int i = 1 ; i <= n ; i ++){
		vector<int > v;
		for(int j = 1 ; j <= m ; j ++){
			int t;cin>>t;
			v.push_back(t);
		}
		if(!mp.count(v)){
			mp[v] = idx++;
			ans.push_back({1,v});
		}
		else{
			ans[mp[v]].cnt++;
		}
	}
	cout<<ans.size()<<"\n";
	sort(ans.begin(),ans.end());
	for(int i = 0 ; i < idx ; i ++){
		cout<<ans[i].cnt;
		for(auto it : ans[i].v){
			cout<<" "<<it;
		}
		cout<<"\n";
	}
	return 0;
}

7-7 插松枝

题解

一个松枝 由 K 个 松枝片组成，松枝片长度必须从下到上依次递减。

工人每次从 N 个物品的传送带上取下一个松枝片，插入当前的松枝干(不限数量)上。

此外，还有一个临时存放松枝片的小盒子，小盒子最多存放M个松枝片。小盒子上若有松枝片，优先级高于传送带。

将松枝放到成品篮，制作下一个松枝片 的情况如下：

（1）小盒子已经满了，但传送带上取到的松针仍然不满足要求。

（2）小盒子中最上面的松针不满足要求，但推送器上已经没有松针了。

（3）松枝干上松针数量达到K个。

代码

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
#include<bits/stdc++.h>
using namespace std;

int n,m,k;
vector<vector<int > > ans;
vector<int > temp;
stack<int > s;
queue<int > q;

// 判断插入松针片x是否合法
bool judge(int x){
	if(temp.empty()) return true;
	if(x <= temp.back()) return true;
	return false;
}

// 插入松针片x到当前松枝干上
void insert(int x){
	temp.push_back(x);
	if(temp.size() == k){
		ans.push_back(temp);
		temp.clear();
	}
}

// 清理当前松枝干，存入答案列表
void clear_cur(){
	if(!temp.empty()){
		ans.push_back(temp);
		temp.clear();
	}
}

void print(){
	for(auto v : ans){
		if(!v.empty()) cout<<v.front();
		for(int i = 1 ; i < v.size() ; i ++){
			cout<<" "<<v[i];
		}
		cout<<"\n";
	}
}

int main(void){
	cin>>n>>m>>k;
	for(int i = 1 ; i <= n ; i ++){
		int t; cin>>t;
		q.push(t);
	}
	// 推送器还有松针
	while(!q.empty()){
		if(!s.empty() && judge(s.top()) ){
			insert(s.top());
			s.pop();
			continue;
		}
		if(!q.empty() && judge(q.front())){
			insert(q.front());
			q.pop();
		}else{
			if(s.size() < m){
				s.push(q.front());
				q.pop();
			}else{
				clear_cur();
			}
		}
	}
	// 清理小盒子里剩下的松针片
	while(!s.empty()){
		if(judge(s.top())){
			insert(s.top()); s.pop();
		}else{
			clear_cur();
		}
	}
	clear_cur();
	print();
	return 0;
}

7-8 老板的作息表

题解

给定一个作息表，格式如下：

1
2
3
4
5
N
hh:mm:ss - hh:mm:ss
hh:mm:ss - hh:mm:ss
...
hh:mm:ss - hh:mm:ss

要求该作息表未涵盖的一天内的时间段【一天指的是00:00:00 - 23:59:59】。

代码

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
#include<bits/stdc++.h>
using namespace std;

struct record{
	int t1,t2;
	bool operator<(const record & rhs){
		return t1 < rhs.t1;
	}
};

int n;
deque<record> dq;

void print(int t1, int t2){
	printf("%02d:%02d:%02d - %02d:%02d:%02d\n",
		t1/3600,(t1%3600)/60,t1%60, t2/3600,(t2%3600)/60,t2%60);
}

int main(void){
	scanf("%d", &n);
	for(int i = 1 ; i <= n ; i ++){
		int h1,m1,s1,h2,m2,s2;
		scanf("%d:%d:%d - %d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);
		int sum1 = h1*3600 + m1*60 + s1;
		int sum2 = h2*3600 + m2*60 + s2;
		dq.push_back({sum1, sum2});
	}
	sort(dq.begin(), dq.end());
	int f = 23*3600 + 59*60 + 59;
	dq.push_front({0,0});
	dq.push_back({f,f});
	for(int i = 0 ; i < dq.size()-1 ; i ++){
		if(dq[i].t2 != dq[i+1].t1){
			print(dq[i].t2, dq[i+1].t1);
		}
	}
	return 0;
}
题解 > GPLT > 分类练习
#模拟 #GPLT
GPLT团体程序设计天梯赛分类练习2：排序+栈+队列
https://czwcugb.github.io/题解/GPLT/GPLT-Sort-Stack-Queue/
作者
ChenZhiwei
发布于
2025年2月21日
许可协议