title: ACM-NEFU新生训练2-排序和CMP
tags:

  • NEFUOJ
  • ACM
  • 排序
    abbrlink: cd7c5106
    date: 2020-12-22 20:15:10

A.谁考了第k名-排序

Description

  1. 在一次考试中，每个学生的成绩都不相同，现知道了每个学生的学号和成绩，求考第k名学生的学号和成绩。

Input

  1. 第一行有两个整数，分别是学生的人数n（1≤n≤100），和求第k名学生的k（1≤k≤n）。
  2. 其后有n行数据，每行包括一个学号（整数）和一个成绩（浮点数），中间用一个空格分隔。

Output

  1. 输出第k名学生的学号和成绩，中间用空格分隔。（注：请用%g输出成绩）

Sample Input

  1. 5 3
  2. 90788001 67.8
  3. 90788002 90.3
  4. 90788003 61
  5. 90788004 68.4
  6. 90788005 73.9

Sample Output

  1. 90788004 68.4

代码

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. struct student
  6. {
  7.     int num;
  8.     double grade;
  9. }s[100];
  11. int cmp(student s1,student s2)
  12. {
  13.     return s1.grade>s2.grade;
  14. }
  16. int main()
  17. {
  18.     int n,k;
  19.     cin>>n>>k;
  20.     for(int i=0;i<n;i++)
  21.     {
  22.         cin>>s[i].num>>s[i].grade;
  23.     }
  24.     sort(s,s+n,cmp);
  25.     printf("%d %g",s[k-1].num,s[k-1].grade);
  26.     return 0;
  27. }

B.奇数单增序列

Description

  1. 给定一个长度为N（不大于500）的正整数序列，请将其中的所有奇数取出，并按升序输出

Input

  1. 共2行：
  2. 第1行为 N；
  3. 第2行为 N 个正整数，其间用空格间隔。

Output

  1. 增序输出的奇数序列，数据之间以逗号间隔。数据保证至少有一个奇数。

Sample Input

  1. 10
  2. 1 3 2 6 5 4 9 8 7 10

Sample Output

  1. 1,3,5,7,9

代码

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. int main()
  6. {
  7.     int n,num[500],flag=1;
  8.     cin>>n;
  9.     for(int i=0;i<n;i++)
  10.     {
  11.         cin>>num[i];
  12.     }
  13.     sort(num,num+n);
  14.     for(int i=0;i<n;i++)
  15.     {
  16.         if(num[i]%2)
  17.         {
  18.             if(!flag)printf(",");
  19.             printf("%d",num[i]);
  20.             flag=0;
  21.         }
  22.     }
  23.     return 0;
  24. }

C.成绩排序

Description

  1. 给出班里某门课程的成绩单，请你按成绩从高到低对成绩单排序输出，如果有相同分数则名字字典序小的在前。

Input

  1. 第一行为n (0 &lt; n &lt; 20)，表示班里的学生数目；
  2. 接下来的n行，每行为每个学生的名字和他的成绩, 中间用单个空格隔开。名字只包含字母且长度不超过20，成绩为一个不大于100的非负整数。

Output

  1. 把成绩单按分数从高到低的顺序进行排序并输出，每行包含名字和分数两项，之间有一个空格。

Sample Input

  1. 4
  2. Kitty 80
  3. Hanmeimei 90
  4. Joey 92
  5. Tim 28

Sample Output

  1. Joey 92
  2. Hanmeimei 90 
  3. Kitty 80
  4. Tim 28

代码

  1. #include<bits/stdc++.h>
  3. using namespace std;
  5. struct student
  6. {
  7.     char name[30];
  8.     int grade;
  9. }a[50];
  11. int cmp(student s1,student s2)
  12. {
  13.     if(s1.grade!=s2.grade)    return s1.grade>s2.grade;
  14.     else return strcmp(s1.name,s2.name)<0;
  15. }
  17. int main()
  18. {
  19.     int n;
  20.     cin>>n;
  21.     for(int i=0;i<n;i++)
  22.     {
  23.         cin>>a[i].name>>a[i].grade;
  24.     }
  25.     sort(a,a+n,cmp);
  26.     for(int i=0;i<n;i++)
  27.     {
  28.         cout<<a[i].name<<" "<<a[i].grade<<endl;
  29.     }
  30.     return 0;
  31. }

D.没必要的排序1

Description

  1. 羽裳有n个数，她想知道前k大的数的和为多少

Input

  1. 首先输入两个数n，k，代表有n个数，求前k大的和，接下来输入n个数，这n个数或是0或是1.
  2. 1&lt;=k&lt;=n&lt;=1000

Output

  1. 输出一个数，为前k大的和

Sample Input

  1. 5 3
  2. 0 0 1 0 1

Sample Output

  1. 2

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int main()
  5. {
  6.     int n,k,cnt=0,tmp;
  7.     while(cin>>n>>k)
  8.     {
  9.         cnt=0;
  10.         for(int i=0;i<n;i++)
  11.         {
  12.             cin>>tmp;
  13.             if(tmp)cnt++;
  14.         }
  15.         if(cnt<k)cout<<cnt<<endl;
  16.         else cout<<k<<endl;
  17.     }
  18.     return 0;
  19. }

E.没必要的排序2

Description

  1. 羽裳有n个数，她想知道前k大的数的和是多少

Input

  1. 输入n，k代表有n个数，求前k大的和,之后输入n个数，第i个数为a[i]
  2. 1&lt;=n&lt;=10000000(1e7)
  3. 1&lt;=k&lt;1000
  4. 对任意的i
  5. 1&lt;=a[i]&lt;=100000(1e5)

Output

  1. 输出一个数ans，ans是前k大数的和

Sample Input

  1. 2 1
  2. 99999 1

Sample Output

  1. 99999

Hint

  1. 排序会超时

思路

hint都有了，必然桶排序

Code

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. int a[100010];
  6. typedef long long ll;
  8. int main()
  9. {
  10.     memset(a,0,sizeof(a));
  11.     int n,k,tmp;
  12.     ll ans=0;
  13.     scanf("%d %d",&n,&k);
  14.     for(int i=0;i<n;i++)
  15.     {
  16.         scanf("%d",&tmp);
  17.         a[tmp]++;
  18.     }
  19.     tmp=ans=0;
  20.     for(int i=100000;i>=1;i--)
  21.     {
  22.         for(int j=a[i];j>0;j--)
  23.         {
  24.             ans+=i;
  25.             k--;
  26.             if(k==0)break;
  27.         }
  28.         if(k==0)break;
  29.     }
  30.     cout<<ans<<endl;
  31.     return 0;
  32. }

F.老和尚的导员

Description

  1. 等小和尚回来后，老和尚居然没有睡觉。老和尚表示他的导员的excel表格坏掉了（老和尚居然有导员？好吧……据说是方丈），而且老和尚的导员要老和尚将寺中所有和尚的期末考试成绩按降序排列来发奖学金（和尚还有奖学金？）
  2. 不用多说，为了继续睡午觉，这个任务理所当然的落在了小和尚身上。所有……你继续帮忙吧。

Input

  1. 寺中主要考试科目有C语言，线性代数，高等数学和英语四个科目（怎么当和尚都这么累），输入的第一行是和尚的人数N（N&lt;=100)，第二行至第N+1行分别为C语言a[i]，线性代数b[i]，高等数学c[i]和英语的成绩d[i](0 &lt;= a[i],b[i],c[i],d[i] &lt;= 100)。

Output

  1. 现需要你将和尚们的成绩以总成绩降序排列，输出数据的每行有两个数字，第一个数字为和尚的编号（输入时的第一个和尚成绩即为和尚1，第二个为和尚2），第二个数字为和尚的总成绩（如果总成绩相同，则按C语言的成绩排列，如在相同，则按线性代数输出编号，以此类推。）

Sample Input

  1. 5
  2. 98 50 27 65
  3. 58 52 24 16
  4. 98 96 90 89
  5. 31 65 98 78
  6. 65 67 66 90

Sample Output

  1. 3 373
  2. 5 288
  3. 4 272
  4. 1 240
  5. 2 150

Code

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. struct score
  6. {
  7.     int num;
  8.     int c;
  9.     int xxds;
  10.     int gdsx;
  11.     int yy;
  12.     int sum;
  13. }p[100];
  15. int cmp(score h1, score h2)
  16. {
  17.     if(h1.sum!=h2.sum)return h1.sum>h2.sum;
  18.     if(h1.c != h2.c)return h1.c > h2.c;
  19.     if(h1.xxds!=h2.xxds)return h1.xxds>h2.xxds;
  20.     if(h1.gdsx!=h2.gdsx)return h1.gdsx>h2.gdsx;
  21.     if(h1.yy!=h2.yy)return h1.yy>h2.yy;
  22. }
  24. int main()
  25. {
  26.     int n;
  27.     while(cin>>n)
  28.     {
  29.         for(int i=0;i<n;i++)
  30.         {
  31.             p[i].num=i+1;
  32.             cin >> p[i].c >> p[i].xxds >> p[i].gdsx >> p[i].yy;
  33.             p[i].sum= p[i].c + p[i].xxds + p[i].gdsx + p[i].yy;
  34.         }
  35.         sort(p,p+n,cmp);
  36.         for(int i=0;i<n;i++)
  37.         {
  38.             cout<<p[i].num<<" "<<p[i].sum<<endl;
  39.         }
  40.     }
  41.     return 0;
  42. }

G.健忘的老和尚

Description

  1. 当小和尚排完名单后，老和尚突然一拍脑袋：“导员把每个人的人名都给我了，可我忘记告诉你了。”好吧……我们可怜的小和尚看来要费二遍事了（好像之前的任务都是你帮他做的，好吧，你真可怜）

Input

  1. 输入数据为多组，输入的第一行为和尚的人数N，可以得到奖学金的人数M，和需要补考的人数O（在这里可以满足M+O&lt;=N，即得到奖学金的和尚一定不用参加补考）。之后的N行每行都有一个字符串（即为和尚的名字，长度小于100）和尚考试的总分a[i](0 &lt;= a[i] &lt;= 1000)。

Output

  1. 前M行，每行是获得奖学金的小和尚的名字；
  2. 后O行，每行是补考的小和尚的名字；
  3. 由于老和尚觉得很对不起小和尚，所以他决定这次简单些，所以无论是奖励还是惩罚都按照总成绩从低到高输出和尚的名字即可。

Sample Input

  1. 5 1 2
  2. a 192 
  3. aa 212
  4. ab 351
  5. bab 128
  6. bbaa 654

Sample Output

  1. bbaa
  2. bab
  3. a

Code

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. struct score
  6. {
  7.     int grade;
  8.     char name[110];
  9. }p[10000];
  11. int cmp(score h1, score h2)
  12. {
  13.     return h1.grade>h2.grade;
  14. }
  16. int main()
  17. {
  18.     int n,m,o;
  19.     while(cin>>n>>m>>o)
  20.     {
  21.         for(int i=0;i<n;i++)
  22.         {
  23.             getchar();
  24.             cin>>p[i].name>>p[i].grade;
  25.         }
  26.         sort(p,p+n,cmp);
  27.         for(int i=m-1;i>=0;i--)
  28.         {
  29.             cout<<p[i].name<<endl;
  30.         }
  31.         for(int i=n-1;i>=n-o;i--)
  32.         {
  33.             cout<<p[i].name<<endl;
  34.         }
  35.     }
  36.     return 0;
  37. }

H.戏说三国

Description

  1.    东汉末年，宦官当权，民不聊生。灵帝中平元年，张角兄弟发动黄巾起义，官军闻风丧胆。为抵抗黄巾，幽州太守刘焉出榜招兵。榜文前，刘备、关羽、张飞三兄弟萍水相逢。三人都有为国效力之心，于是桃园结为异姓兄弟，开始了一段三国浪漫传奇……
  2.   如果我问你三国中谁最聪明你一定会说是诸葛亮，我要问你谁武功最高，保不准你就要说关羽。是啊，我们的刘备对于优秀的手下向来十分满意。可是有一天，刘备在无意间在朋友圈里看到了梁山的宋江正在进行英雄排座次，最可气的是这条动态已经被转发评论了无数次了……这一下可气坏了刘备，他决定也来一次，蜀中文武百官大排名。
  3. 为了公平起见，诸葛亮帮他制定一条评分标准：每个官员有一个智育、德育、武育三个分数，分别以b%，a%，c%的比率计入加权总分，按总分降序排列，总分相同按智育折合后的分数降序，智育相同按德育，依次类推最终决定排名。（保证没有排名一样的两个人）

Input

  1. 输入第一行t(1&lt;=t&lt;=1000)表示输入的组数。接下来每组第一行1个整数n（1&lt;=n&lt;=100000）三个实数a,b,c(a+b+c=100)接下来n行每行包括英雄的名字，字符串s（1&lt;=len&lt;=20,全为小写字母） 智育、德育、武育的分数（整数）。（1~100）

Output

  1. 每组第一行输出是第几组输出Case #t：接下来输出n行每行包括英雄的名字，总分，智育、德育、武育折合后的分数（保留四位小数）。

Sample Input

  1. 1
  2. 3 20.00  20.00  60.00
  3. zhugeliang 90 80 0
  4. zhangfei 0 0 100
  5. guanyu 10 100 100

Sample Output

  1. Case #1:
  2. guanyu 82.0000 2.0000 20.0000 60.0000
  3. zhangfei 60.0000 0.0000 0.0000 60.0000
  4. zhugeliang 34.0000 18.0000 16.0000 0.0000

Code

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. struct haohan
  6. {
  7.     double sum;
  8.     double zy;
  9.     double dy;
  10.     double wy;
  11.     char name[21];
  12. }p[1010];
  14. int cmp(haohan p1, haohan p2)
  15. {
  16.     return p1.sum>p2.sum;
  17. }
  19. int main()
  20. {
  21.     int t,n;
  22.     double a,b,c;
  23.     cin>>t;
  24.     for(int i=0;i<t;i++)
  25.     {
  26.         cin>>n>>a>>b>>c;
  27.         for(int j=0;j<n;j++)
  28.         {
  29.             cin>>p[j].name>>p[j].zy>>p[j].dy>>p[j].wy;
  30.             p[j].zy*=b/100;
  31.             p[j].dy*=a/100;
  32.             p[j].wy*=c/100;
  33.             p[j].sum=p[j].zy+p[j].dy+p[j].wy;
  34.         }
  35.         sort(p,p+n,cmp);
  36.         printf("Case #%d:\n",i+1);
  37.         for(int j=0;j<n;j++)
  38.         {
  39.             printf("%s %.4lf %.4lf %.4lf %.4lf\n",p[j].name,p[j].sum,p[j].zy,p[j].dy,p[j].wy);
  40.         }
  41.     }
  42.     return 0;
  43. }

I.相约摩洛哥

Description

  1. 2015年5月ACM全球总决赛在摩洛哥卡萨布兰卡举行，到时会有来自世界各地的acm大牛齐聚摩洛哥。
  3. 作为本次大赛的举办方负责人阿焜和阿祥被分配给了一个重要的任务，就是在比赛中统计大家的排名。
  4. acm大赛排名规则（摘自百度百科）：
  5.     最后的获胜者为正确解答题目最多且总用时最少的队伍。每道试题用时将从竞赛开始到试题解答被判定为正确为止，其间每一次提交运行结果被判错误的话将被加罚20分钟时间，未正确解答的试题不记时。例如：A、B两队都正确完成两道题目，其中A队提交这两题的时间分别是比赛开始后1:00和2:45，B队为1:20和2:00，但B队有一题提交了2次。这样A队的总用时为1:00+2:45=3:45而B队为1:20+2:00+0:20=3:40，所以B队以总用时少而获胜。
  6. 请你帮他俩完成这项任务吧！（保证没有成绩完全相同两支队伍）

Input

  1. 多组输入，每组一个正整数n（1&lt;=n&lt;=100000），代表有n个队伍参赛。接下来的n行，每行分别有一个字符串（只包含小写英文字母）作为队伍名，长度1&lt;=len&lt;=10;ABC三道题的ac时间（以分钟为单位），时间为-1表示该题没有ac。接下来又有n行，表示每道题的提交次数,用3个正整数表示。

Output

  1. 输出排行榜。n行，每行一个队伍的名字、解题数和总用时。

Sample Input

  1. 3    
  2. team 30 10 20
  3. behappy 20 20 90
  4. newbee 15 16 17
  5. 1 1 1
  6. 1 1 10
  7. 1 1 1

Sample Output

  1. newbee 3 48
  2. team 3 60
  3. behappy 3 310

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. struct team
  5. {
  6.     char name[11];
  7.     int ta,tb,tc;
  8.     int actime;
  9.     int num;
  10. }t[100010];
  12. int cmp(team t1,team t2)
  13. {
  14.     if(t1.num!=t2.num)return t1.num>t2.num;
  15.     return t1.actime < t2.actime;
  16. }
  18. int main()
  19. {
  20.     int n,a,b,c;
  21.     while(cin>>n)
  22.     {
  23.         for(int i=0;i<n;i++)
  24.         {
  25.             cin>>t[i].name>>t[i].ta>>t[i].tb>>t[i].tc;
  26.         }
  27.         for(int i=0;i<n;i++)
  28.         {
  29.             cin>>a>>b>>c;
  30.             t[i].actime=0;
  31.             t[i].num=0;
  32.             if(t[i].ta!=-1)
  33.             {
  34.                 t[i].ta+=20*(a-1);
  35.                 t[i].num++;
  36.                 t[i].actime+=t[i].ta;
  37.             }
  38.             if(t[i].tb!=-1)
  39.             {
  40.                 t[i].tb+=20*(b-1);
  41.                 t[i].num++;
  42.                 t[i].actime+=t[i].tb;
  43.             }
  44.             if(t[i].tc!=-1)
  45.             {
  46.                 t[i].tc+=20*(c-1);
  47.                 t[i].num++;
  48.                 t[i].actime+=t[i].tc;
  49.             }
  50.         }
  51.         sort(t,t+n,cmp);
  52.         for(int i=0;i<n;i++)
  53.         {
  54.             cout << t[i].name << " " << t[i].num << " " << t[i].actime << endl;
  55.         }
  56.     }
  57.     return 0;
  58. }

J.结构体排序题一

Description

  1. 现在给定一组二维平面上面的点的坐标,保证它的坐标是int类型的整数且大于等于0小于等于99.请你按照数据所给要求进行排序.
  2. 首先先以横坐标进行排序,若横坐标相同则按纵坐标排序,降序或升序将以0和1的形式表示,0表示降序,1表示升序.
  3. 比如,若数据开头给出0 1的要求,则表示先以横坐标降序排列,若横坐标相同则按纵坐标升序排列.
  4. 再比如,若数据开头给出1 1的要求,则表示先以横坐标升序排列,若横坐标相同则按纵坐标升序排列.
  5. 保证点的数量大于等于3小于等于99

Input

  1. 第1行包含三个数字,第一个数字和第二个数字分别表示横坐标和纵坐标的排序要求,0表示降序,1表示升序,第三个数字n表示有几个点需要排序.
  2. 余下第2~n+1行每行各有两个类型为n个点的坐标,例如第2行第一个数字表示第一个点横坐标,第二个数字表示第一个点的纵坐标.

Output

  1. 输出n行坐标,一行表示一个点,格式如下:
  2. (x0,y0)

Sample Input

  1. 0 0 4
  2. 1 1
  3. 1 2
  4. 2 1
  5. 2 2
  6. 1 1 4
  7. 2 2
  8. 2 1
  9. 1 2
  10. 1 1

Sample Output

  1. (2,2)
  2. (2,1)
  3. (1,2)
  4. (1,1)
  5. (1,1)
  6. (1,2)
  7. (2,1)
  8. (2,2)

Code

  1. #include<bits/stdc++.h>
  3. using namespace std;
  5. struct node
  6. {
  7.     int x;
  8.     int y;
  9. }a[110];
  11. int rey,rex;
  13. int cmp(node t1,node t2)
  14. {
  15.     if(rex)
  16.     {
  17.         if(t1.x!=t2.x)  return t1.x<t2.x;
  18.         if(rey) return t1.y<t2.y;
  19.         else    return t1.y>t2.y;
  20.     }
  21.     else
  22.     {
  23.         if(t1.x!=t2.x)  return t1.x>t2.x;
  24.         if(rey) return t1.y<t2.y;
  25.         else    return t1.y>t2.y;
  26.     }
  27. }
  29. int main()
  30. {
  31.     int n;
  32.     while(cin>>rex>>rey>>n)
  33.     {
  34.         for(int i=0;i<n;i++)
  35.         {
  36.             cin>>a[i].x>>a[i].y;
  37.         }
  38.         sort(a,a+n,cmp);
  39.         for(int i=0;i<n;i++)
  40.         {
  41.             printf("(%d,%d)\n",a[i].x,a[i].y);
  42.         }
  43.     }
  44.     return 0;
  45. }

K.最强编码同学票数统计

Description

  1. 为了找出林大2020新生中最擅长编写代码的同学，学校发起了一场投票。通过同学报名、前期遴选等环节，共提名了100名同学作为选举人进行评选，假设他们的编号从1到100。现在学院已经采集到了n名同学的投票结果，请你找出得票最多的程序员获得的票数(注：就是让你找相同数字的个数的最大值)。

Input

  1. 输入：
  2. 第一行一个数n(1≤n≤100) , 代表有多少位同学投票。
  3. 第二行n个数:a1,a2⋯an,  ai(1≤ai≤100)代表第i位同学投票所选的林大最擅长编码的那个程序员的编号。输入数据有多组！

Output

  1. 输出：
  2. 每组数据的输出占一行 , 输出得票最多的那个同学获得的票数（相同编号的个数的最大值）。

Sample Input

  1. 输入样例1：
  2. 6
  3. 1 2 4 7 7 7
  4. 4
  5. 5 5 5 5

Sample Output

  1. 输出样例1：
  2. 3
  3. 4

Code

  1. #include<bits/stdc++.h>
  3. using namespace std;
  5. int a[110];
  7. int main()
  8. {
  9.     int n;
  10.     while(cin>>n)
  11.     {
  12.         memset(a,0,sizeof(a));
  13.         for(int i=1;i<=n;i++)
  14.         {
  15.             int tmp;
  16.             cin>>tmp;
  17.             a[tmp]++;
  18.         }
  19.         int ans=0;
  20.         for(int i=1;i<=100;i++)
  21.         {
  22.             ans=max(ans, a[i]);
  23.         }
  24.         cout<<ans<<endl;
  25.     }
  26.     return 0;
  27. }