思维之海

——在云端,寻找我的星匙。

普及-排序

将杂乱无章的数据变得有规律。有各种各样的排序算法,看情况使用。

P1177 【模板】快速排序

题目描述

利用快速排序算法将读入的NNN个数从小到大排序后输出。

快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料,掌握后独立完成。(C++选手请不要试图使用STL,虽然你可以使用sort一遍过,但是你并没有掌握快速排序算法的精髓。)

Code $O(n^2)\longrightarrow O(nlogn)$ 分类快排LGU

算法3:最常用的排序——快速排序- 坐在马桶上学算法- 极客学院Wiki

快速排序实现及优化| DualPivotQuicksort | 「浮生若梦」 - sczyh30’s blog

此题用纯粹的经典快排过不了。(哪怕加上随机选取)

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
#include<bits/stdc++.h>
using namespace std;
int n;
void swap(int &a, int &b){
int tmp = a;
a = b;
b = tmp;
}

void quicksort(vector<int> &a, int le, int ri){
if(le >= ri - 1) return;
int i = le - 1, j = le - 1, pivot = ri - 1, r = (rand()%(ri-le))+le;
swap(a[pivot], a[r]); // 随机化处理
while(++j < pivot){
if(a[j] < a[pivot])
swap(a[++i], a[j]);
}
swap(a[i + 1], a[pivot]);
quicksort(a, le, i+1);
quicksort(a, i+2, ri);
}


int main() {
cin >> n;

vector<int> a;
for( int i = 0 ; i < n; ++i){
int tmp; cin >> tmp;
a.push_back(tmp);
}

quicksort(a, 0, n);
for (int i = 0; i < n; ++i){
printf("%d%c", a[i], " \n"[i==n-1]);
}

return 0;
}

Code $O(n^2)\longrightarrow O(nlogn)$ 双向快排LUG

作者: 沧海之耀
更新时间: 2018-02-06 21:11

在Ta的博客查看

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

void swap(int &a, int &b){
int tmp = a; a = b; b = tmp;
}

void quicksort(vector<int> &a, int le, int ri){
int i = le, j = ri - 1, Pivot = a[(rand()%(ri-le))+le];
while(i <= j){ // 双指针分类
while(a[i]<Pivot) i++;
while(a[j]>Pivot) j--;
if(i<=j) swap(a[i++],a[j--]);
}
if(le < j ) quicksort(a, le, j+1);
if(i < ri-1) quicksort(a, i, ri);
}


int main() {
int n; cin >> n;

vector<int> a;
for( int i = 0 ; i < n; ++i){
int tmp; cin >> tmp;
a.push_back(tmp);
}

quicksort(a, 0, n);
for (int i = 0; i < n; ++i){
printf("%d%c", a[i], " \n"[i==n-1]);
}

return 0;
}

P1059 明明的随机数

题目描述

明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了N个1到1000之间的随机整数(N≤100),对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

Code $O(n^2+n)\longrightarrow 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
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;

void swap(int &a, int &b){
int tmp = a; a = b; b = tmp;
}

void quicksort(vector<int> &a, int le, int ri){
int i = le, j = ri - 1, Pivot = a[(rand()%(ri-le))+le];
while(i <= j){ // 双指针分类
while(a[i]<Pivot) i++;
while(a[j]>Pivot) j--;
if(i<=j) swap(a[i++],a[j--]);
}
if(le < j ) quicksort(a, le, j+1);
if(i < ri-1) quicksort(a, i, ri);
}

int unique(vector<int> &a, int le, int ri){
int i = 0, j = 0;
while(++j < ri){
if(a[j] != a[i] && ++i != j)
a[i] = a[j];
}
return i;
}


int main() {
int n; cin >> n;

vector<int> a;
for( int i = 0 ; i < n; ++i){
int tmp; cin >> tmp;
a.push_back(tmp);
}

quicksort(a, 0, n);
int u = unique(a, 0, n) + 1;

cout<<u<<endl;
for (int i = 0; i < u; ++i){
printf("%d%c", a[i], " \n"[i==u-1]);
}

return 0;
}

P1068 分数线划定 模拟+排序

题目描述

世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才,A市对所有报名的选手进行了笔试,笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的150%划定,即如果计划录取m名志愿者,则面试分数线为排名第$m×150\%$(向下取整)名的选手的分数,而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。

现在就请你编写程序划定面试分数线,并输出所有进入面试的选手的报名号和笔试成绩。

NOIP 2009 普及组 第二题

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

struct Candidate{
int ID, Grade;
Candidate(int a,int b){
ID = a; Grade = b;
}
};

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

int main(){
int n, m; cin >> n >> m;
vector<Candidate> person;
for(int i = 0; i < n; ++i){
int a, b; cin >> a >> b;
Candidate tmp(a,b);
person.push_back(tmp);
}
sort(person.begin(), person.end(), cmp);

int Line, People;
People = m*3/2;
while(People < n && person[People -1].Grade == person[People].Grade) People++; // 考虑重分的情况
Line = person[People - 1].Grade;
cout << Line << " " << People <<endl;
for(int i = 0; i < People; ++i){
cout << person[i].ID << " " << person[i].Grade <<endl;
}

return 0;
}

P1781 宇宙总统

题目背景

宇宙总统竞选

题目描述

地球历公元6036年,全宇宙准备竞选一个最贤能的人当总统,共有n个非凡拔尖的人竞选总统,现在票数已经统计完毕,请你算出谁能够当上总统。

Code $O(n)$

优先选位数更长的string。如果位数一样,则比较字典序。

注:位数不一样时,string的字典序从头依次比较,因而失效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;

int main(){
int n;
vector<string> tickets;
cin >> n;
for(int i = 0; i < n; ++i){
string tmp; cin >> tmp;
tickets.push_back(tmp);
}

int ret = 0;
for(int i = 1; i < n; ++i){
if(tickets[ret].length() < tickets[i].length()) ret = i;
else if(tickets[ret].length() == tickets[i].length() && tickets[ret] < tickets[i]) ret = i;
}

cout<< ret+1 << endl << tickets[ret] <<endl;
return 0;
}