题目内容
对于在中国大学MOOC(http://www.icourse163.org/) 学习“数据结构”课程的学生，想要获得一张合格证书，总评成绩必须达到 60 分及以上，并且有另加福利：总评分在 [G, 100] 区间内者，可以得到 50 元 PAT 代金券；在 [60, G) 区间内者，可以得到 20 元PAT代金券。全国考点通用，一年有效。同时任课老师还会把总评成绩前 K 名的学生列入课程“名人堂”。本题就请你编写程序，帮助老师列出名人堂的学生，并统计一共发出了面值多少元的 PAT 代金券。
输入格式
输入在第一行给出 3 个整数，分别是 N（不超过 10 000 的正整数，为学生总数）、G（在 (60,100) 区间内的整数，为题面中描述的代金券等级分界线）、K（不超过 100 且不超过 N 的正整数，为进入名人堂的最低名次）。接下来 N 行，每行给出一位学生的账号（长度不超过15位、不带空格的字符串）和总评成绩（区间 [0, 100] 内的整数），其间以空格分隔。题目保证没有重复的账号。
输出格式
首先在一行中输出发出的 PAT 代金券的总面值。然后按总评成绩非升序输出进入名人堂的学生的名次、账号和成绩，其间以 1 个空格分隔。需要注意的是：成绩相同的学生享有并列的排名，排名并列时，按账号的字母序升序输出。
输入样例
输出样例
时间限制：150ms内存限制：65536kb
代码
解法一
用一个结构体来存姓名和成绩，再用自定义的比较函数sort一下。
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct stu
{
string name;
int grade;
};
bool cmp(const stu& s1, const stu& s2)
{
if(s1.grade != s2.grade)
return s1.grade > s2.grade;
else
return s1.name < s2.name;
}
int main()
{
cin.sync_with_stdio(false);
int n, g, k;
cin >> n >> g >> k;
vector<stu> v;
ll ans = 0;
for(int i = 0; i < n; i++)
{
string temp1;
int temp2;
cin >> temp1 >> temp2;
stu temp;
temp.name = temp1;
temp.grade = temp2;
v.push_back(temp);
if(temp2 >= 60)
{
if(temp2 < g)
ans += 20;
else
ans += 50;
}
}
cout << ans << endl;
int index = 1;
int number = 1;
sort(v.begin(), v.end(), cmp);
vector<stu>::iterator t;
ll flag = v[0].grade;
for(t = v.begin(); t != v.end(); t++)
{
if(flag != (*t).grade)
{
flag = (*t).grade;
index = number;
}
if(index > k)
break;
cout << index << " " << (*t).name << " " << (*t).grade << endl;
number++;
}
return 0;
}
|
解法二
用一个map<string,name>来存name和grade,将map转存到vcetor到中进行排序。
比赛的时候好蠢好蠢的做法，后面会说。
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool cmp (const pair<string,int>& a,const pair<string,int>& b)
{
if(a.second!=b.second)
return a.second>b.second;
else
return a.first<b.first;
}
int main()
{
cin.sync_with_stdio(false);
int n,g,k;
cin>>n>>g>>k;
map<string,int> m;
ll ans=0;
for(int i=0;i<n;i++)
{
string temp1;
int temp2;
cin>>temp1>>temp2;
m.insert(pair<string,int>(temp1,temp2));
if(temp2>=60)
{
if(temp2<g)
ans+=20;
else
ans+=50;
}
}
cout<<ans<<endl;
vector<pair<string,int>> mm(m.begin(),m.end());
sort(mm.begin(),mm.end(),cmp);
int index=1;
int number=1;
vector<pair<string,int>>::iterator t=mm.begin();
ll flag=(*t).second;
for(t=mm.begin();t!=mm.end();t++)
{
if(flag!=(*t).second)
{
flag=(*t).second;
index=number;
}
if(index>k)
break;
cout<<index<<" "<<(*t).first<<" "<<(*t).second<<endl;
number++;
}
return 0;
}
|
总结
比赛的时候没看清题意，上来就直接一个map，快写完了的时候才发现不对，然后就突发奇想的对map进行sort，但是编译的时候比较函数那一行一直报错。我到现在都不清楚为什么比赛的时候要一直死磕对map按照value进行sort，就是懒得改成结构体加vector，结果直到比赛结束前几分钟才开始改，虽然改完了可惜没时间交了。
回到宿舍终于在网上找到了对map进行sort的方法：将map转存至vector中，然后sort。vector<pair<string,int>> mm(m.begin(),m.end());但是还是用结构体加vector方便啊。
还是自己菜啊.......
注意：STL库中的sort函数只能对线性存储的对象进行排序,如:vector、array、list、deque,不能对集合容器进行排序,如:set、map;
参考博客:C++ STL中Map的按Key排序和按Value排序
