Fork me on GitHub

PAT(甲级)渡劫(十六)-Mice and Rice(30)


PAT(甲级)渡劫(十六)-Mice and Rice(30)

题目大意:

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
题目意思是:
n个人,每人手中拿着一个数字,然后按照k人一组进行比赛,谁的数大谁就赢,最后输出他们的排名

输入说明:
第一行是n,k,分别代表参赛人数和一个组的最大人数
第二行是n个数据,比如这里,就是从010号参赛选手的手中的数字
第三行是n个参赛选手的顺序,分组就是依据此来划分

详细说明:

11 3 //11个参赛选手,3人一组

以下数据中,第一行代表参赛选手的序号,第二行代表参赛选手手中的数字

选手序号:00 01 02 | 03 04 05 | 06 07 08 | 09 10
手中数字:25 18 00 | 46 37 03 | 19 22 57 | 56 10

第一局:
比赛次序:06 00 08 | 07 10 05 | 09 01 04 | 02 03 rank->06 00 10 05 01 04 02 :5
对应数字:19 25 57 | 22 10 03 | 56 18 37 | 00 46

第二局:
08 07 09 | 03 rank->07 09 :3
57 22 56 | 46

第三局:
08 03 rank->03:2
57 46

第四局:
08 rank->08:1
57

结果:
00 01 02 03 04 05 06 07 08 09 10

代码如下:

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
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

vector<int> nums,ranks;
vector<int> MiceAndRice(vector<int> &v,int k){
int n = v.size(); // 本局参赛人数
int groupnum = (n%k == 0)?n/k:n/k+1; // 小组数量
vector<int> nextv; // 晋级选手
for(int i = 1 ; i <= groupnum ; i++){// 每个小组进行比赛
vector<int>::iterator itb = v.begin() + (i-1)*k; // 每个小组的开始序号
vector<int>::iterator ite = min(v.end(),itb+k);
vector<int>::iterator it = itb,maxit = itb; // maxit记录最大值
while(it != ite){
if(nums[*maxit] < nums[*it])
maxit = it;
++it;
}
nextv.push_back(*maxit); // 有最大的数字的选手晋级
while(itb != ite){
ranks[*itb++] = groupnum+1; // 排名
}
}
return nextv;
}

int main(){
//freopen("in.txt","r",stdin);
int n,k;
cin>>n>>k;
nums.resize(n);
ranks.resize(n);
vector<int> v(n); // 记录选手编号
for(int i = 0 ; i < n ; i++){
cin>>nums[i];
}
for(int i = 0 ; i < n ; i++){
cin>>v[i];
}
while(v.size() > 1){
v = MiceAndRice(v,k);
}
ranks[v[0]] = 1;
for(int i = 0 ; i < n ; i++){
if(i == n-1){
cout<<ranks[i];
}else{
cout<<ranks[i]<<" ";
}
}

return 0;
}

运行结果:

坚持原创技术分享,您的支持将鼓励我继续创作
-------------本文结束感谢您的阅读-------------
0%