【洛谷题单算法1-2】P1271\P1177\P1923\P1059\P1093
P1271 【深基9.例1】选举学生会
题目描述
学校正在选举学生会成员，有 n(n≤999)n(n\le 999)n(n≤999) 名候选人，每名候选人编号分别从 1 到 n，现在收集到了 m(m<=2000000)m(m<=2000000)m(m<=2000000) 张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。
输入格式
输入 n 和 m 以及 m 个选票上的数字。
输出格式
求出排序后的选票编号。
输入输出样例
输入
5 10
2 5 2 2 5 2 2 2 1 2
输出
1 2 2 2 2 2 2 2 5 5
代码如下
#include
using namespace std;
int a[1010];
int main(){int n,m,i,j,x;cin>>n>>m;for(i=1; i<=m; i++){ //输入投票数据 cin>>x;a[x]+=1;} for(i=1; i<=n; i++){ //n个学生，每个学生相当于一个桶 for(j=1; j<=a[i]; j++){ //每个学生的投票数 cout< P1177 【模板】快速排序
题目描述
利用快速排序算法将读入的 N 个数从小到大排序后输出。
快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++ 选手请不要试图使用 STL，虽然你可以使用 sort 一遍过，但是你并没有掌握快速排序算法的精髓。）
输入格式
第 1 行为一个正整数 N，第 2 行包含 N 个空格隔开的正整数 aia_iai ，为你需要进行排序的数，数据保证了 aia_iai 不超过 10910^9109 。
输出格式
将给定的 N 个数从小到大输出，数之间空格隔开，行末换行且无空格。
输入输出样例
输入
5
4 2 4 5 1
输出
1 2 4 4 5
代码如下
#include
using namespace std;
const int MAXN=100000010;
int a[MAXN];
int i,j,l,r; //l左边界 r右边界
int n,flag,temp;void qsort(int a[], int l, int r){i=l,j=r,flag=a[(i+j)/2];do{while(a[i]flag) j--; //找到第一个不大于flag的数 if(i<=j){temp=a[i],a[i]=a[j],a[j]=temp;i++,j--;}}while(i<=j);if(lcin>>n;for(i=1; i<=n; i++){ //输入投票数据 cin>>a[i];} qsort(a,1,n);for(i=1; i<=n; i++){ //n个学生，每个学生相当于一个桶 cout< P1923 【深基9.例4】求第 k 小的数
题目描述
输入 n（1≤n<50000001 \le n < 50000001≤n<5000000 且 n 为奇数）个数字 aia_iai （1≤ai<1091 \le a_i < {10}^91≤ai<109 ），输出这些数字的第 k 小的数。最小的数是第 0 小。
输入输出样例
输入
5 1
4 3 2 1 5
输出
2
代码如下
#include
using namespace std;int a[5000005];
int i,j,l,r;
int n,k,flag,temp,ans;
inline int read(){//快速读入
//加快程序运行效率，调用函数实际上是在内存调用。加上inline编译时，会写进主函数。 int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9'){ //不是数字继续读入 //if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;
}
void qqsort(int l,int r){i=l,j=r,flag=a[(i+j)/2];do{while(a[i]flag) j--;if(i<=j){temp=a[i],a[i]=a[j],a[j]=temp;i++,j--;}}while(i<=j);if(k+1<=j) qqsort(l,j); //第k小的数字在左侧区间 位置从0开始 else if(k+1>=i) qqsort(i,r);//第k小的数字在右侧区间 else cout<cin>>n>>k; //n为数据个数，k为第k小的数 for(i=1; i<=n; i++) {a[i]=read();}qqsort(1,n);return 0;
}
P1059 [NOIP2006 普及组] 明明的随机数
题目描述
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 N 个 1 到 1000 之间的随机整数 (N≤100)(N\leq100)(N≤100) ，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
输入格式
输入有两行，第 1 行为 1 个正整数，表示所生成的随机数的个数 N。
第 2 行有 N 个用空格隔开的正整数，为所产生的随机数。
输出格式
输出也是两行，第 1 行为 1 个正整数 M，表示不相同的随机数的个数。
第 2 行为 M 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。
输入输出样例
输入
10
20 40 32 67 40 20 89 300 400 15
输出
8
15 20 32 40 67 89 300 400
代码如下
#include
using namespace std;
int n,a[1010];
int i,x,cnt;
//输入数据范围为[1,1000]
int main(){cin>>n;for(i=1; i<=n; i++){cin>>x;a[x]+=1;}for(i=1; i<=1000; i++){ //统计不重复数据的个数 if(a[i] != 0) cnt++;}cout<if(a[i] != 0) cout< P1093 [NOIP2007 普及组] 奖学金
题目描述
某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前 5 名学生发奖学金。期末，每个学生都有 3 门课的成绩:语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学 排在前面，这样，每个学生的排序是唯一确定的。
任务：先根据输入的 3 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。注意，在前 5 名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据(每行输出两个数:学号、总分) 是:
777 279279279
555 279279279
这两行数据的含义是:总分最高的两个同学的学号依次是 7 号、55 号。这两名同学的总分都是 279 (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为 7 的学生语文成绩更高一些。如果你的前两名的输出数据是:
555 279279279
777 279279279
则按输出错误处理，不能得分。
输入格式
共 n+1行。
第 1 行为一个正整数n(≤300)n ( \le 300)n(≤300) ，表示该校参加评选的学生人数。
第 2 到 n+1 行，每行有 3 个用空格隔开的数字，每个数字都在 0 到 100 之间。第 j 行的 3 个数字依次表示学号为 j−1j−1j−1 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为 1∼n1\sim n1∼n（恰好是输入数据的行号减 1）。
输出格式
共 5 行，每行是两个用空格隔开的正整数，依次表示前 5 名学生的学号和总分。
输入输出样例
输入
6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98
输出
6 265
4 264
3 258
2 244
1 237
代码如下
#include
using namespace std;int n,i,j,temp;struct student{int chi,math,eng,id,sumn;
}stu[310];int main(){cin>>n;for(i=1; i<=n; i++){cin>>stu[i].chi>>stu[i].math>>stu[i].eng;stu[i].id=i;stu[i].sumn=stu[i].chi+stu[i].math+stu[i].eng;}for(i=1; i<=n; i++){for(j=1; j<=n-i; j++){if(stu[j].sumnstu[j+1].id)swap(stu[j],stu[j+1]);}}for(i=1; i<=5; i++){cout<
上一篇：虚拟机扩容——非LVM分区