noip第20课作业

时间:2023-03-10 04:56:48
noip第20课作业

1. 评学习小标兵

【问题描述】

东东所在的班级有 N 名同学,期末考试进行了数学、语文、英语、地理四门功课的测试。班主任要将这 N 名学生中总分前三名定为本学期的“学习小标兵”。现在给出这N 名学生的姓名和各科成绩,请你编程找到总分前三名,并依次输出他们的姓名。所给数据不会有总分相同的情况(使用快速排序完成)。

【输入格式】

输入包含 N+1 行,第一行仅有一个正整数 N (N≤40),表示东东班里学生的总数,接下来的 N 行,每行描述一个学生的考试信息,依次为姓名、数学成绩、语文成绩、英语成绩与地理成绩,两两之间用一个空格分隔。注意:姓名(不会同名)都用小写字母表示(不超过 10 个字母),成绩全都是不超过 200 的非负整数。

【输出格式】

输出包含三行,每行仅包含一个学生的姓名,依次为第一名到第三名学生的姓名。

【样例输入】

4

jing 98 90 87 74

ming 96 92 85 97

jun 95 78 56 91

hong 95 100 85 78

【样例输出】

ming

hong

jing

#include<iostream>
using namespace std;
struct p {
char name[];
int math;
int chinese;
int eglish;
int geo;
int sum;
};
p a[];
void quick_sort(int left,int right) {
if(left >= right) return;
int i = left;
int j = right;
p x = a[left];
while(i < j) {
while(i < j && a[j].sum < x.sum)
j--;
a[i] = a[j];
while(i < j && a[i].sum > x.sum)
i++;
a[j] = a[i];
}
a[i] = x;
quick_sort(left,i-);
quick_sort(i+,right);
}
int main() {
int n,f=,s=,i,j;
cin>>n;
for(i=; i<n; i++) {
cin>>a[i].name>>a[i].math>>a[i].chinese>>a[i].eglish>>a[i].geo;
a[i].sum = a[i].math+a[i].chinese+a[i].eglish+a[i].geo;
}
quick_sort(,n-);
for(i=; i<; i++)
cout<<a[i].name<<endl; return ;
}

2.挑选宇宙总统

【问题描述】

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

【输入格式】

第一行为一个整数n,代表竞选总统的人数。

接下来有n行,分别为第一个候选人到第n个候选人的票数。

【输出格式】

共两行,第一行是一个整数m,为当上总统的人的号数。

第二行是当上总统的人的选票。

说明:票数小于10000位数字。n<=20

【样例输入】

5

98765

12365

87954

1022356

985678

【样例输出】

4

1022356

#include<iostream>
#include<cstring>
#include<algorithm>
const int maxn=;
using namespace std;
struct node{
string s;
int id;
} a[maxn];
bool cmp(node x,node y){
if(x.s.size()==y.s.size())
return x.s>y.s;
else return x.s.size()>y.s.size();
}
int main(){
int n;
cin >> n;
for(int i=;i<=n;++i)
cin>>a[i].s,a[i].id=i;
sort(a+,a++n,cmp);
cout<<a[].id<<endl<<a[].s;
return ;
}

1.排序算法

【问题描述】

快速排序和归并排序算法是信息学竞赛的必备算法。对于快速排序和归并排序算法还不是很熟练的同学需要多多练习,掌握后独立完成。

【输入格式】

输入文件sort.in的第一行为一个正整数N,(1 ≤ N ≤ 100000)

第二行包含N个空格隔开的正整数,为你需要进行排序的数,每个数据保证不超过100000000。

【输出格式】

输出文件sort.out将给定的N个数从大到小输出,数之间使用空格隔开,行末换行并且没有空格。

【样例输入】

5

4 2 4 5 1

【样例输出】

5 4 4 2 1

#include <fstream>
using namespace std;
ifstream cin("sort.in");
ofstream cout("sort.out");
int a[],n;
void quick_sort(int left,int right){
if(left >= right) return;
int i = left;
int j = right;
int x = a[left];
while(i < j){
while(i < j && x <= a[j]) j--;
a[i] = a[j];
while(i < j && x >= a[i]) i++;
a[j] = a[i];
}
a[i] = x;
quick_sort(left,i-);
quick_sort(i+,right);
}
int main(){
cin >> n;
for(int i = ;i < n;i++){
cin >> a[i];
}
quick_sort(,n-);
for(int i = n-;i >=;i--){
cout << a[i] << " ";
}
cin.close();
cout.close();
return ;
}