新手入门刷题（专题二）排序
4.12
宇宙总统
题目描述
地球历公元 6036 年，全宇宙准备竞选一个最贤能的人当总统，共有 n个非凡拔尖的人竞选总统，现在票数已经统计完毕，请你算出谁能够当上总统。
输入样例
5 //参赛人数
98765 //得票数 票数可能会很大，可能会到 100位数字。
12365
87954
1022356
985678
输出样例
4
1022356
思路
本题的票数用string存储，比较时先比较票长，长度一致则比较大小。
代码
#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct Candidate {
int num;//序号
string grade;//票数
} pre[25];
//自定义比较函数
bool cmp(Candidate a,Candidate b){
if(a.grade.length()>b.grade.length()) return a.grade.length()>b.grade.length();
else if(a.grade.length()==b.grade.length()) return a.grade>b.grade;
return false;
}
int main() {
cin>>n;
for(int i=1;i<=n;i++) {
cin>>pre[i].grade;
pre[i].num = i;
}
sort(pre+1,pre+n+1,cmp);
cout<<pre[1].num<<endl<<pre[1].grade;
return 0;
}
[USACO07DEC]Bookshelf B
题目描述
略，求最少几个奶牛即可到书架高度
输入样例
6 40 //奶牛数为6，书架高为40
6 //第一个奶牛高度
18
11
13
19
11
输出样例
3
思路
先快排所有奶牛高度，再从大到小相加，直到>=书架高度，统计相加的奶牛个数
代码
#include <iostream>
#include<algorithm>
using namespace std;
int n,b,h[20020],t,k;
//快排模板要记住
int qs(int q[],int l,int r){
if(l>=r) return q[l];
int i = l-1,j = r+1, x = q[l+r>>1];
while(i<j){
do i++;while(q[i]<x);
do j--;while(q[j]>x);
if(i<j) swap(q[i],q[j]);
}
qs(q, l, j);
qs(q, j + 1, r);
}
int main() {
cin>>n>>b;
for(int i=0;i<n;i++) cin>>h[i];
qs(h,0,n-1);
while(t<b&&k<n){
t += h[n-1-k];
k++;
}
cout<<k;
return 0;
}
车厢重组
题目描述
好家伙，考查冒泡可还行。
代码
#include <iostream>
#include<algorithm>
using namespace std;
int n,t[10010],times;
int main() {
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&t[i]);
}
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(t[i]>t[j]) {
swap(t[i],t[j]);
times++;
}
}
}
printf("%d",times);
return 0;
}
欢乐的跳
题目描述
一个包含n个元素的整数数组，如果数组两个连续元素之间差的绝对值包括了[1,n-1]之间的所有整数，则称之符合“欢乐的跳”，如数组 {1，4，2，3} 符合“欢乐的跳”，因为差的绝对值分别为：3,2,1。
给定一个数组，你的任务是判断该数组是否符合“欢乐的跳”。
输入样例
5 1 4 2 -1 6 //第一个数字代表数组长度，之后代表每一个数字
输出样例
jolly //符合“欢乐的跳”输出
Not jolly //不符合“欢乐的跳”输出
思路
数组长度 n ( 1 ≤ n ≤ 1000 )
数组中的数字范围 [-100000000，100000000]
本题提供两种解法
第一种用桶装两数之差，即采用数组下标的方式存储两数之差，不过数组的长度要大于100000000。
只需要数组范围 [1,n-1] 之内的数全是 1 即符合“欢乐的跳”，具体见代码一。
第二种方法，我们可以研究一下题目，显然在存数组的过程中即可计算两数之差，一旦两数之差出现重复，一定不符合“欢乐的跳”，具体见代码二。
代码一
#include <iostream>
#include<algorithm>
using namespace std;
int n,t[1010],num[200000000];
int main() {
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&t[i]);
}
//桶
for(int i=0;i<n-1;i++){
int tmp;
tmp = t[i]>=t[i+1]?t[i]-t[i+1]:t[i+1]-t[i];
num[tmp]++;
}
for(int i=1;i<n;i++){
if(num[i]==0){
printf("Not jolly");
return 0;
}
}
printf("Jolly");
return 0;
}
代码二
#include <iostream>
using namespace std;
int n,a,b,c;
bool d[1010];
int main() {
//输入数组长度
scanf("%d",&n);
//输入第一个数
scanf("%d",&a);
//从第二个数开始输入
for(int i=1;i<n;i++){
scanf("%d",&b);
//计算两数之差
c = a>=b?a-b:b-a;
//两数之差不在[1,n-1]之内，必定不符合
if(c>=1&&c<=n-1){
//判断是否重复，重复也必定不符合
if(d[c]) {
printf("Not jolly");
return 0;
}
//不重复，则继续
else d[c] = true;
}else {
printf("Not jolly");
return 0;
}
//赋值第二个数给第一个数，开启下轮循环
a = b;
}
//能够完成输入循环，则必定符合
printf("Jolly");
return 0;
}
4.13
[NOIP2009 普及组] 分数线划定
题目描述
世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的 150% 划定，即如果计划录取m名志愿者，则面试分数线为排名第 m×150%（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。
现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。
输入样例
6 3 //报名参加笔试的选手总数 计划录取的志愿者人数
1000 90 //选手的报名号 选手的笔试成绩
3239 88
2390 95
7231 84
1005 95
1001 88
输出样例
88 5
1005 95
2390 95
1000 90
1001 88
3239 88
//按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。
说明/提示
【样例说明】
m×150%=3×150%=4.5，向下取整后为4。保证4个人进入面试的分数线为88，但因为88有重分，所以所有成绩大于等于88 的选手都可以进入面试，故最终有5个人进入面试。
思路
学习新排序啦, 归并排序, 时间复杂度nlogn, 稳定!!!
快排时间复杂度为nlogn, 但是不稳定, 本题如果成绩相同时按输入先后顺序输出, 则使用快排不合适, 因为不稳定会导致成绩相同但是输出顺序与输入顺序不一致.
但是本题要求根据 成绩从大到小 和 成绩相同则根据编号从小到大输出, 因此使用 快排 和 归并排序 皆可
归并排序模板
const int N=1e6+10;
int q[N],temp[N];
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;
int mid = (l + r) >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
//正序
if (q[i] <= q[j]) tmp[k++] = q[i++];
//逆序
//if (q[i] >= q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
while (i <= mid) tmp[k++] = q[i++];
while (j <= r) tmp[k++] = q[j++];
for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}
采用归并排序解题代码
#include<iostream>
using namespace std;
struct Emp{
int num;
int grade;
}emp[5050],tmp[5050];
int n,m;
//根据归并排序模板修改，稳定
void merge_sort(int l, int r)
{
if (l >= r) return;
int mid = (l + r) >> 1;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
//成绩从大到小
if (emp[i].grade > emp[j].grade) tmp[k++] = emp[i++];
//成绩相同,编号从小到大
else if (emp[i].grade == emp[j].grade && emp[i].num <= emp[j].num) tmp[k++] = emp[i++];
else tmp[k++] = emp[j++];
while (i <= mid) tmp[k++] = emp[i++];
while (j <= r) tmp[k++] = emp[j++];
for (int i = l, j = 0; i <= r; i++, j++) emp[i] = tmp[j];
}
int main(){
scanf("%d%d",&n,&m);
m = m * 1.5;
for(int i=1;i<=n;i++) scanf("%d%d",&emp[i].num,&emp[i].grade);
merge_sort(1,n);
//成绩相同时接着往下找
while(emp[m].grade==emp[++m].grade);
printf("%d %d\n",emp[m].grade,--m);
for(int i=1;i<=m;i++) printf("%d %d\n",emp[i].num,emp[i].grade);
return 0;
}
采用快排解题代码
#include<iostream>
using namespace std;
struct Emp{
int num;
int grade;
}emp[5050];
int n,m;
//改写快排
void qs(int l,int r){
if(l>=r) return;
int i = l-1, j = r+1, x = emp[(r+l)>>1].grade, y = emp[(r+l)>>1].num;
while(i<j){
//成绩从大到小 成绩相同,编号从小到大
do i++;while(emp[i].grade>x||(emp[i].grade==x&&emp[i].num<y));
do j--;while(emp[j].grade<x||(emp[j].grade==x&&emp[j].num>y));
if(i<j) swap(emp[i],emp[j]);
}
qs(l,j);
qs(j+1,r);
}
int main(){
scanf("%d%d",&n,&m);
m = m * 1.5;
for(int i=1;i<=n;i++) scanf("%d%d",&emp[i].num,&emp[i].grade);
qs(1,n);
//成绩相同时接着往下找
while(emp[m].grade==emp[++m].grade);
printf("%d %d\n",emp[m].grade,--m);
for(int i=1;i<=m;i++) printf("%d %d\n",emp[i].num,emp[i].grade);
return 0;
}
攀爬者
题目描述
HKE考完GDOI之后跟他的神犇小伙伴们一起去爬山。
他在地形图上标记了N个点，每个点Pi都有一个坐标(xi,yi,zi)。所有点对中，高度值z不会相等。HKE准备从最低的点爬到最高的点，他的攀爬满足以下条件：
(1) 经过他标记的每一个点；
(2) 从第二个点开始，他经过的每一个点高度z都比上一个点高；
(3) HKE会飞，他从一个点Pi爬到Pj的距离为两个点的欧几里得距离。即，
( X i − X j ) 2 + ( Y i − Y j ) 2 + ( Z i − Z j ) 2 \sqrt{(X_i-X_j)^2+(Y_i-Y_j)^2+(Z_i-Z_j)^2} (Xi−Xj)2+(Yi−Yj)2+(Zi−Zj)2
现在，HKE希望你能求出他攀爬的总距离。
输入样例
5 //点的个数
2 2 2 //x y z
1 1 1
4 4 4
3 3 3
5 5 5
输出样例
6.928
说明/提示
【样例说明】
对于100%的数据，1≤N≤50000，答案的范围在double范围内。
思路
先按照z轴排序, 再计算两点距离.
代码
#include<iostream>
#include<math.h>
#include<cmath>
#include<algorithm>
using namespace std;
double ans;
struct Node {
int x,y,z;
//重载<
bool operator < (const Node &b)const{
return z<b.z;
}
} a[50050];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
sort(a,a+n);
for(int i=1;i<n;i++) ans+=sqrt(pow(a[i].x-a[i-1].x,2)+pow(a[i].y-a[i-1].y,2)+pow(a[i].z-a[i-1].z,2));
printf("%.3lf",ans);
return 0;
}
4.14
生日
题目描述
cjf
君想调查学校 OI 组每个同学的生日，并按照年龄从大到小的顺序排序，如果有两个同学生日相同,输入靠后的同学先输出。但
cjf
君最近作业很多，没有时间，所以请你帮她排序。
输入样例
3 //人数
Yangchu 1992 4 23 //姓名 生日
Qiujingya 1993 10 13
Luowen 1991 8 1
输出样例
Luowen //姓名
Yangchu
Qiujingya
说明/提示
数据规模
1<n<100
length(s)<20
思路
结构体加sort函数，本题和上一题基本一样。
代码
#include<iostream>
#include<algorithm>
using namespace std;
struct Students {
int nu;
char na[25];
int ye;
int mo;
int da;
//sort默认从小到大排序，我们需要重载 < 运算符号
//重载<
bool operator < (const Students &b)const{
if(ye<b.ye) return ye<b.ye;
else if(ye==b.ye&&mo<b.mo) return mo<b.mo;
else if(ye==b.ye&&mo==b.mo&&da<b.da) return da<b.da;
else if(ye==b.ye&&mo==b.mo&&da==b.da&&nu>b.nu) return nu>b.nu;
return false;
}
} a[110];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
a[i].nu = i;
//提供两种输入方法
//小知识,字符串名称本身就是地址，无需添加地址符
// scanf("%s %d %d %d",a[i].na,&a[i].ye,&a[i].mo,&a[i].da);
cin>>a[i].na>>a[i].ye>>a[i].mo>>a[i].da;
}
sort(a,a+n);
for(int i=0;i<n;i++) printf("%s\n",a[i].na);
return 0;
}
[NOIP1998 提高组] 拼数
题目描述
设有 n个正整数 a1…an，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。
输入样例
4
7 13 4 246
输出样例
7424613
说明/提示
对于全部的测试点，保证
1 ≤ n ≤ 20 1≤n≤20 1≤n≤20
1 ≤ a i ≤ 1 0 9 1≤ai≤10^9 1≤ai≤109
思路
只需要判段两数先后相加的大小即可。
代码
#include<iostream>
#include<algorithm>
using namespace std;
string s[25];
//
bool cmp(string a,string b){
return a+b>b+a;
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) cin>>s[i];
sort(s,s+n,cmp);
for(int i=0;i<n;i++) cout<<s[i];
return 0;
}
![Windows下VS开发环境环境安装工程项目设置关于Debug和Release的提示[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)