普及-排序Ex

这里的排序就更上一层了。不仅融合了别的算法与技巧,排序本身也有各种花招。

P1583 魔法照片

题目描述

一共有n(n≤20000)个人(以1—n编号)向佳佳要照片,而佳佳只能把照片给其中的k个人。佳佳按照与他们的关系好坏的程度给每个人赋予了一个初始权值W[i]。然后将初始权值从大到小进行排序,每人就有了一个序号D[i](取值同样是1—n)。按照这个序号对10取模的值将这些人分为10类。也就是说定义每个人的类别序号C[i]的值为(D[i]-1) mod 10 +1,显然类别序号的取值为1—10。第i类的人将会额外得到E[i]的权值。你需要做的就是求出加上额外权值以后,最终的权值最大的k个人,并输出他们的编号。在排序中,如果两人的W[i]相同,编号小的优先。

Code $O(nlogn)$

只能说是辣鸡题目了。什么玩意儿嘛。。

原始——排序——加值——再排序——输出原始编号。

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 person{
int ID, w;
};

bool cmp(person x, person y){
return x.w == y.w ? x.ID < y.ID : x.w > y.w;
}

int main(){
int n, k, E[11];
vector<person> W;

cin >> n >> k;
for (int i = 1; i <= 10; ++i)
cin >> E[i];
for(int i = 0; i < n; ++i){
int t; cin >> t;
person tmp; tmp.ID = i + 1; tmp.w = t;
W.push_back(tmp);
}

sort(W.begin(), W.end(), cmp);

for(int i = 0; i < n; ++i){
W[i].w += E[i%10 + 1];
}

sort(W.begin(), W.end(), cmp);

for(int i = 0; i < k; ++i)
cout << W[i].ID << " \n"[i == n-1];


return 0;
}

P1051 谁拿了最多奖学金

题目描述

某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种,获取的条件各自不同:

  1. 院士奖学金,每人8000元,期末平均成绩高于80分(>80),并且在本学期内发表1篇或1篇以上论文的学生均可获得;
  2. 五四奖学金,每人4000元,期末平均成绩高于85分(>85),并且班级评议成绩高于80分(>80>80>80)的学生均可获得;
  3. 成绩优秀奖,每人2000元,期末平均成绩高于90分(>90)的学生均可获得;
  4. 西部奖学金,每人1000元,期末平均成绩高于85分(>85)的西部省份学生均可获得;
  5. 班级贡献奖,每人850元,班级评议成绩高于80分(>80)的学生干部均可获得;

只要符合条件就可以得奖,每项奖学金的获奖人数没有限制,每名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是87分,班级评议成绩82分,同时他还是一位学生干部,那么他可以同时获得五四奖学金和班级贡献奖,奖金总数是4850元。

现在给出若干学生的相关数据,请计算哪些同学获得的奖金总数最高(假设总有同学能满足获得奖学金的条件)。

Code $O(n)$

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

struct Student{
string Name;
int final_grade, class_grade, papers;
char isOffical, isWest;
};


int main(){
int n; cin >> n;
vector<Student> Data;
for(int i = 0; i < n; ++i){
Student tmp;
cin >> tmp.Name >> tmp.final_grade >> tmp.class_grade >> tmp.isOffical >> tmp.isWest >> tmp.papers;
Data.push_back(tmp);
}

string Best_name;
int Best_amount = 0, Total_amount = 0;
for(int i = 0; i < n; ++i){
int amount = 0;
if(Data[i].final_grade > 80 && Data[i].papers >= 1) amount += 8000;
if(Data[i].final_grade > 85 && Data[i].class_grade > 80) amount += 4000;
if(Data[i].final_grade > 90) amount += 2000;
if(Data[i].final_grade > 85 && Data[i].isWest == 'Y') amount += 1000;
if(Data[i].class_grade > 80 && Data[i].isOffical == 'Y') amount += 850;

if(amount > Best_amount){
Best_amount = amount;
Best_name = Data[i].Name;
}
Total_amount += amount;
}

cout << Best_name <<endl;
cout << Best_amount << endl;
cout << Total_amount <<endl;

return 0;
}

P1093 奖学金

题目描述

某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末,每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序,如果两个同学总分相同,再按语文成绩从高到低排序,如果两个同学总分和语文成绩都相同,那么规定学号小的同学 排在前面,这样,每个学生的排序是唯一确定的。

任务:先根据输入的3门课的成绩计算总分,然后按上述规则排序,最后按排名顺序输出前五名名学生的学号和总分。注意,在前5名同学中,每个人的奖学金都不相同,因此,你必须严格按上述规则排序。例如,在某个正确答案中,如果前两行的输出数据(每行输出两个数:学号、总分) 是:

7 279
5 279

这两行数据的含义是:总分最高的两个同学的学号依次是777号、555号。这两名同学的总分都是 279 (总分等于输入的语文、数学、英语三科成绩之和) ,但学号为777的学生语文成绩更高一些。如果你的前两名的输出数据是:

5 279
7 279

则按输出错误处理,不能得分。

Code $O(n)$

总排序 $O(nlogn)$

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

struct person{
int ID, chinese, math, english, total;
};

bool cmp(person x, person y){
return x.total == y.total ?
(x.chinese == y.chinese ? x.ID < y.ID : x.chinese > y.chinese)
: x.total > y.total;
}

int main(){
int n; cin >> n;
vector<person> P;
for(int i = 0; i < n; ++i){
int c, m, e;
cin >> c >> m >> e;
person tmp;
tmp.ID = i+1; tmp.chinese = c; tmp.english = e; tmp.math = m;
tmp.total = c + m + e;
P.push_back(tmp);
}

sort(P.begin(), P.end(), cmp);

for(int i = 0; i < 5; ++i){
cout << P[i].ID <<" "<< P[i].total<<endl;
}

return 0;
}

堆 $O(n+5logn)$

关于priority_queue似乎不能直接传递比较器,而只能借助重载operator <来实现比较。

1577507936811

注意到compare参数是一个类,因此比较器必须至少封装一个struct里面。

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

struct person{
int ID, chinese, math, english, total;
};

bool operator <(person x, person y){
return !(x.total == y.total ?
(x.chinese == y.chinese ? x.ID < y.ID : x.chinese > y.chinese)
: x.total > y.total);
}

int main(){
int n; cin >> n;
priority_queue<person> P;
for(int i = 0; i < n; ++i){
int c, m, e;
cin >> c >> m >> e;
person tmp;
tmp.ID = i+1; tmp.chinese = c; tmp.english = e; tmp.math = m;
tmp.total = c + m + e;
P.push(tmp);
}

for(int i = 0; i < 5; ++i){
cout << P.top().ID <<" "<< P.top().total<<endl;
P.pop();
}

return 0;
}

P1309 瑞士轮

题目背景

在双人对决的竞技性比赛,如乒乓球、羽毛球、国际象棋中,最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少,每场都紧张刺激,但偶然性较高。后者的特点是较为公平,偶然性较低,但比赛过程往往十分冗长。

本题中介绍的瑞士轮赛制,因最早使用于1895年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折中,既保证了比赛的稳定性,又能使赛程不至于过长。

题目描述

2×N名编号为 1∼2N 的选手共进行R 轮比赛。每轮比赛开始前,以及所有比赛结束后,都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的,约定编号较小的选手排名靠前。

每轮比赛的对阵安排与该轮比赛开始前的排名有关:第1 名和第2 名、第 3 名和第 4名、……、第2K−1名和第2K 名、…… 、第2N−1名和第2N名,各进行一场比赛。每场比赛胜者得1分,负者得0分。也就是说除了首轮以外,其它轮比赛的安排均不能事先确定,而是要取决于选手在之前比赛中的表现。

现给定每个选手的初始分数及其实力值,试计算在R 轮比赛过后,排名第Q的选手编号是多少。我们假设选手的实力值两两不同,且每场比赛中实力值较高的总能获胜。

Code $O(RN+NlogN)$

注意题目中的限制。N约为10万,则logN约为16;R约为50。

可知,$R\times NlogN \approx 50\times 10^5\times 16\approx 10^7$。

同时,$RN+NlogN \approx 50\times 10^5 + 10^5\times 16 \approx 10^6$。

可见本题是在卡常数。

Force $O(R\times NlogN)$ 40%

R轮比赛,每次比赛完成都需要重排序。

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

struct person{
int ID, grade, power;
};

bool cmp(person x, person y){
return x.grade == y.grade ? x.ID < y.ID : x.grade > y.grade;
}

int main(){
int N, R, Q; cin >> N >> R >> Q;
vector<person> P;
for(int i = 0; i < 2*N; ++i){
int grade; cin >> grade;
person tmp;
tmp.ID = i + 1; tmp.grade = grade;
P.push_back(tmp);
}
for(int i = 0; i < 2*N; ++i){
cin >> P[i].power;
}

for(int i = 0; i < R; ++i){
for(int i = 0; i < N; ++i){
if(P[2*i].power > P[2*i + 1].power) P[2*i].grade++;
else P[2*i + 1].grade++;
}
sort(P.begin(), P.end(), cmp);
}

cout << P[Q-1].ID<<endl;

return 0;
}

归并排序 $O(RN+NlogN)$

注意到每次比赛后有一定的保序性存在。每轮的所有胜者/败者保序,只需$O(n)$时间归并这两个子序列。

注意到第一次也要排序

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

struct person{
int ID, grade, power;
};

bool cmp(person x, person y){
return x.grade == y.grade ? x.ID < y.ID : x.grade > y.grade;
}

int main(){
int N, R, Q; cin >> N >> R >> Q;
vector<person> P;
for(int i = 0; i < 2*N; ++i){
int grade; cin >> grade;
person tmp;
tmp.ID = i + 1; tmp.grade = grade;
P.push_back(tmp);
}
for(int i = 0; i < 2*N; ++i){
cin >> P[i].power;
}

sort(P.begin(), P.end(), cmp); // 初始排序,O(nlogn)

for(int i = 0; i < R; ++i){
vector<person> a, b; // a胜,b败
// compete
for(int i = 0; i < N; ++i){
if(P[2*i].power > P[2*i + 1].power){
P[2*i].grade++;
a.push_back(P[2*i]);
b.push_back(P[2*i+1]);
}
else{
P[2*i + 1].grade++;
a.push_back(P[2*i+1]);
b.push_back(P[2*i]);
}
}
// merge
int ii,j,k; ii = j = k = 0;
while(j < N && k < N){
if(cmp(a[j], b[k])) P[ii++] = a[j++];
else P[ii++] = b[k++];
}
while(j < N) P[ii++] = a[j++];
while(k < N) P[ii++] = b[k++];
}

cout << P[Q-1].ID<<endl;

return 0;
}
0%