ACM.结构体排序和桶排序

￡神魔★判官ぃ 2023-06-28 11:09 23阅读 0赞

\#结构体排序

\#\#sort函数  
sort是c++自带函数  
复杂度 n\*log(n)  
包含在头文件  
\#include的c++标准库里  
函数有三个参数  
1.要排序的数组的起始地址  
2.数组的结束地址  
3.第三个参数是排序的方法，可以不写，默认是从小到大  
4.从小到大可以写成sort（a，a+n，less<数据类型>）  
5.从大到小可写成sort（a,a+n,greater<数据类型>）

\#\#\#cmp函数写法  
比如按照成绩高低排序从高到低  
bool cmp1(stu a,stu b)  
\{  
return a.chengji>b.chengji;  
\}

\#桶排序  
过程好理解，主要为开一个大数组每一项初始值记录为0，每当出现对应的数字是，对应元素++。  
代码如下：

#include<stdio.h>
    int main()
    {
        
        int a[11],i,j;
        for(i=0;i<11;i++)
        {
        
            a[i]=0;
        }
        int n;//人数
        scanf("%d",&n);
        int t;//用t接收分数
        for(i=0;i<n;i++)
        {
        
           scanf("%d",&t);
           a[t]++;
        }
          for(i=0;i<11;i++)
        {
        
            for(j=1;j<=a[i];j++)
            {
        
                printf("%d ",i);
            }
        }
        printf("\n");
        return 0;
    }
    若是从大到小输出则把for(i=0;i<11;i++)改成
    for(i=10;i>=0;i--)即可

--------------------

例题  
1.NEFU-1481  
谁考了第k名-排序  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
在一次考试中，每个学生的成绩都不相同，现知道了每个学生的学号和成绩，求考第k名学生的学号和成绩。  
Input  
第一行有两个整数，分别是学生的人数n（1≤n≤100），和求第k名学生的k（1≤k≤n）。  
其后有n行数据，每行包括一个学号（整数）和一个成绩（浮点数），中间用一个空格分隔。  
Output  
输出第k名学生的学号和成绩，中间用空格分隔。（注：请用%g输出成绩）  
Sample Input  
5 3  
90788001 67.8  
90788002 90.3  
90788003 61  
90788004 68.4  
90788005 73.9  
Sample Output  
90788004 68.4

注意结果以题干要求的%G输出即可。

#include <bits/stdc++.h>
    using namespace std;
    typedef struct stu
    {
        
        int id;
        double cj;
    };
    bool cmp(stu a,stu b)
    {
        
        return a.cj>b.cj;
    }
    int main()
    {
        
        int n,k;
        cin>>n>>k;
        struct stu a[1000];
        for(int i=1;i<=n;i++)
        {
        cin>>a[i].id>>a[i].cj;}
        sort(a+1,a+1+n,cmp);
        printf("%d %g\n",a[k].id,a[k].cj);
        return 0;
    }

二.NEFU-1282  
奇数单增序列  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
给定一个长度为N（不大于500）的正整数序列，请将其中的所有奇数取出，并按升序输出  
Input  
共2行：  
第1行为 N；  
第2行为 N 个正整数，其间用空格间隔。  
Output  
增序输出的奇数序列，数据之间以逗号间隔。数据保证至少有一个奇数。  
Sample Input  
10  
1 3 2 6 5 4 9 8 7 10  
Sample Output  
1,3,5,7,9  
因为数字范围限制在了500之内，可以使用桶排序解决，通常空间小于1e7都可用桶排序。

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        
        int n;
        while(cin>>n)
        {
        
            int a[n];
            int i=0,j=0;
            int b[500];
            for(i=0;i<500;i++)
            {
        
                b[i]=0;
            }
            for(i=0;i<n;i++)
            {
        
                cin>>a[i];
                if((a[i]%2)!=0)
                {
        
                    b[a[i]]++;
                }
            }
            int g=0;
            for(i=0;i<500;i++)
                {
        
                    for(j=0;j<b[i];j++)
                    {
        
                        if(b[i]>=1&&g==0)
                        {
        cout<<i;
                        g++;
                        }
                        else
                        {
        
                            cout<<","<<i;
                        }
                    }
                }
                printf("\n");
        }
        return 0;
    }

三.NEFU-1483  
成绩排序  
Problem:C  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
给出班里某门课程的成绩单，请你按成绩从高到低对成绩单排序输出，如果有相同分数则名字字典序小的在前。  
Input  
第一行为n (0 < n < 20)，表示班里的学生数目；  
接下来的n行，每行为每个学生的名字和他的成绩, 中间用单个空格隔开。名字只包含字母且长度不超过20，成绩为一个不大于100的非负整数。  
Output  
把成绩单按分数从高到低的顺序进行排序并输出，每行包含名字和分数两项，之间有一个空格。  
Sample Input  
4  
Kitty 80  
Hanmeimei 90  
Joey 92  
Tim 28  
Sample Output  
Joey 92  
Hanmeimei 90  
Kitty 80  
Tim 28  
结构体排序基础题，关于名字字典序可以额外在结构体中增加一个变量记录，随着输入顺序赋值即可，注意bool内的写法。

#include <bits/stdc++.h>
    using namespace std;
    typedef struct stu
    {
        
        char id[100];
        int cj;
    };
    bool cmp(stu a,stu b)
    {
        
        if(a.cj!=b.cj)
        {
        return a.cj>b.cj;}
        else
        {
        
            if(strcmp(a.id,b.id)>=0)
            {
        
                return a.id;
            }
            else
            {
        
                return b.id;
            }
        }
    }
    int main()
    {
        
        int n;
        cin>>n;
        struct stu a[1000];
        for(int i=1;i<=n;i++)
        {
        cin>>a[i].id>>a[i].cj;}
        sort(a+1,a+1+n,cmp);
        for(int j=1;j<=n;j++)
        {
        printf("%s %d\n",a[j].id,a[j].cj);}
        return 0;
    }

四NEFU-1659  
没必要的排序1  
Problem:D  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
羽裳有n个数，她想知道前k大的数的和为多少  
Input  
首先输入两个数n，k，代表有n个数，求前k大的和，接下来输入n个数，这n个数或是0或是1.  
1<=k<=n<=1000  
Output  
输出一个数，为前k大的和  
Sample Input  
5 3  
0 0 1 0 1  
Sample Output  
2  
数据很小，可直接使用c++内置的sort函数。  
不写代码了，easy

五.NEFU-1650  
没必要的排序2  
Problem:E  
Time Limit:3000ms  
Memory Limit:65535K  
Description  
羽裳有n个数，她想知道前k大的数的和是多少  
Input  
输入n，k代表有n个数，求前k大的和,之后输入n个数，第i个数为a\[i\]  
1<=n<=10000000(1e7)  
1<=k<1000  
对任意的i  
1<=a\[i\]<=100000(1e5)  
Output  
输出一个数ans，ans是前k大数的和  
Sample Input  
2 1  
99999 1  
Sample Output  
99999  
与上一题的区别为数据范围变大，若仍排序必定超时，所以考虑时间复杂度小的桶排序。

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        
        int n,k;
        while(cin>>n>>k)
        {
        
            int a[n+1];
            int b[100001];
            memset(b,0,sizeof(b));
            for(int i=1;i<=n;i++)
            {
        
                cin>>a[i];
                b[a[i]]++;
            }
            int sum=0,num=0;
            for(int i=100000;i>=1;i--)
            {
        
                if(b[i]>0)//加上所有出现过的数
                {
        
                    sum=sum+b[i]*i;
                    num=num+b[i];
                }
                if(num>=k)//把不符合范围多加的数字减去
                {
        
                    sum=sum-(num-k)*i;
                    break;
                }
            }
            cout<<sum<<endl;
        }
        return 0;
    }

六.NEFU-554  
老和尚的导员  
Problem:F  
Time Limit:1000ms  
Memory Limit:65536K  
Description  
等小和尚回来后，老和尚居然没有睡觉。老和尚表示他的导员的excel表格坏掉了（老和尚居然有导员？好吧……据说是方丈），而且老和尚的导员要老和尚将寺中所有和尚的期末考试成绩按降序排列来发奖学金（和尚还有奖学金？）  
不用多说，为了继续睡午觉，这个任务理所当然的落在了小和尚身上。所有……你继续帮忙吧。  
Input  
寺中主要考试科目有C语言，线性代数，高等数学和英语四个科目（怎么当和尚都这么累），输入的第一行是和尚的人数N（N<=100)，第二行至第N+1行分别为C语言a\[i\]，线性代数b\[i\]，高等数学c\[i\]和英语的成绩d\[i\](0 <= a\[i\],b\[i\],c\[i\],d\[i\] <= 100)。  
Output  
现需要你将和尚们的成绩以总成绩降序排列，输出数据的每行有两个数字，第一个数字为和尚的编号（输入时的第一个和尚成绩即为和尚1，第二个为和尚2），第二个数字为和尚的总成绩（如果总成绩相同，则按C语言的成绩排列，如在相同，则按线性代数输出编号，以此类推。）  
Sample Input  
5  
98 50 27 65  
58 52 24 16  
98 96 90 89  
31 65 98 78  
65 67 66 90  
Sample Output  
3 373  
5 288  
4 272  
1 240  
2 150  
注意各个要素的排序时的位置即可

#include <bits/stdc++.h>
    using namespace std;
    struct stu
    {
        
        int c;
        int xiandai;
        int gaoshu;
        int yingyu;
        int id;
        int sum;
    };
    bool cmp(stu a,stu b)
    {
        
    if(a.sum!=b.sum)
        return a.sum>b.sum;
    else
    {
        
        if(a.c!=b.c)
        {
        
            return a.c>b.c;
        }
        else
        {
        
            if(a.xiandai!=b.xiandai)
            {
        
                return a.xiandai>b.xiandai;
            }
            else
            {
        
                if(a.gaoshu>b.gaoshu)
                {
        
                    return a.gaoshu>b.gaoshu;
                }
                else
                {
        
                    if(a.yingyu!=b.yingyu)
                    {
        
                        return a.yingyu>b.yingyu;
                    }
                }
            }
        }
    }
    }
    int main()
    {
        
        int n;
        while(cin>>n)
        {
        
            struct stu p[n];
            int b[n];
            memset(b,0,sizeof(b));
            for(int i=0;i<n;i++)
            {
        
                p[i].id=i;
                cin>>p[i].c>>p[i].xiandai>>p[i].gaoshu>>p[i].yingyu;
                p[i].sum=p[i].c+p[i].xiandai+p[i].gaoshu+p[i].yingyu;
            }
            sort(p,p+n,cmp);
            for(int i=0;i<n;i++)
            {
        
                cout<<p[i].id+1<<" "<<p[i].sum<<endl;
            }
        }
        return 0;
    }

七.NEFU-556  
健忘的老和尚  
Problem:G  
Time Limit:1000ms  
Memory Limit:65536K  
Description  
当小和尚排完名单后，老和尚突然一拍脑袋：“导员把每个人的人名都给我了，可我忘记告诉你了。”好吧……我们可怜的小和尚看来要费二遍事了（好像之前的任务都是你帮他做的，好吧，你真可怜）  
Input  
输入数据为多组，输入的第一行为和尚的人数N，可以得到奖学金的人数M，和需要补考的人数O（在这里可以满足M+O<=N，即得到奖学金的和尚一定不用参加补考）。之后的N行每行都有一个字符串（即为和尚的名字，长度小于100）和尚考试的总分a\[i\](0 <= a\[i\] <= 1000)。  
Output  
前M行，每行是获得奖学金的小和尚的名字；  
后O行，每行是补考的小和尚的名字；  
由于老和尚觉得很对不起小和尚，所以他决定这次简单些，所以无论是奖励还是惩罚都按照总成绩从低到高输出和尚的名字即可。  
Sample Input  
5 1 2  
a 192  
aa 212  
ab 351  
bab 128  
bbaa 654  
Sample Output  
bbaa  
bab  
a  
思维比较简单，不详述

#include <bits/stdc++.h>
    using namespace std;
    struct stu
    {
        
        char name[100];
        int cj;
    };
    bool cmp(stu a,stu b)
    {
        
        return a.cj>b.cj;
    }
    int main()
    {
        
        int N,M,O;
        while(cin>>N>>M>>O)
        {
        
            struct stu p[N];
            for(int i=0;i<N;i++)
            {
        
                cin>>p[i].name>>p[i].cj;
            }
        sort(p,p+N,cmp);
        for(int i=M-1;i>=0;i--)
        {
        
            cout<<p[i].name<<endl;
        }
        for(int i=N-1;i>=N-O;i--)
        {
        
            cout<<p[i].name<<endl;
        }
        }
        return 0;
    }

八.NEFU-873  
戏说三国  
Problem:873  
Time Limit:1000ms  
Memory Limit:65536K  
Description  
东汉末年，宦官当权，民不聊生。灵帝中平元年，张角兄弟发动黄巾起义，官军闻风丧胆。为抵抗黄巾，幽州太守刘焉出榜招兵。榜文前，刘备、关羽、张飞三兄弟萍水相逢。三人都有为国效力之心，于是桃园结为异姓兄弟，开始了一段三国浪漫传奇……  
如果我问你三国中谁最聪明你一定会说是诸葛亮，我要问你谁武功最高，保不准你就要说关羽。是啊，我们的刘备对于优秀的手下向来十分满意。可是有一天，刘备在无意间在朋友圈里看到了梁山的宋江正在进行英雄排座次，最可气的是这条动态已经被转发评论了无数次了……这一下可气坏了刘备，他决定也来一次，蜀中文武百官大排名。  
为了公平起见，诸葛亮帮他制定一条评分标准：每个官员有一个智育、德育、武育三个分数，分别以b%，a%，c%的比率计入加权总分，按总分降序排列，总分相同按智育折合后的分数降序，智育相同按德育，依次类推最终决定排名。（保证没有排名一样的两个人）  
Input  
输入第一行t(1<=t<=1000)表示输入的组数。接下来每组第一行1个整数n（1<=n<=100000）三个实数a,b,c(a+b+c=100)接下来n行每行包括英雄的名字，字符串s（1<=len<=20,全为小写字母） 智育、德育、武育的分数（整数）。（1~100）  
Output  
每组第一行输出是第几组输出Case \#t：接下来输出n行每行包括英雄的名字，总分，智育、德育、武育折合后的分数（保留四位小数）。  
Sample Input  
1  
3 20.00 20.00 60.00  
zhugeliang 90 80 0  
zhangfei 0 0 100  
guanyu 10 100 100  
Sample Output  
Case \#1:  
guanyu 82.0000 2.0000 20.0000 60.0000  
zhangfei 60.0000 0.0000 0.0000 60.0000  
zhugeliang 34.0000 18.0000 16.0000 0.0000  
注意按照bac的顺序比较，比较坑人。

#include <stdio.h>
    #include <stdlib.h>
    #include <algorithm>
    using namespace std;
    struct hit{
        
    char name[25];
    int zy,dy,e;
    double zhiyu,deyu,wuyu,s;
    }h[1000];
    bool cmp(hit a,hit b)
    {
        
        return a.s>b.s;
    }
    int main()
    {
        
        int n,i,j,t,r;
        float a,b,c;
        scanf("%d",&t);
        for (r=1;r<=t;r++)
        {
        
            scanf("%d%f%f%f",&n,&a,&b,&c);
            a/=100;b/=100;c/=100;
            for (i=0;i<n;i++)
            {
        
                scanf("%s",h[i].name);
                scanf("%d%d%d",&h[i].zy,&h[i].dy,&h[i].e);
                h[i].zhiyu=b*h[i].zy;
                h[i].deyu=a*h[i].dy;
                h[i].wuyu=c*h[i].e;
                h[i].s=h[i].zhiyu+h[i].deyu+h[i].wuyu;
            }
            sort(h,h+n,cmp);
            printf("Case #%d:\n",r);
            for (i=0;i<n;i++)
            {
        
                printf("%s %.4lf %.4lf %.4lf %.4lf\n",h[i].name,h[i].s,h[i].zhiyu,h[i].deyu,h[i].wuyu);
            }
        }
        return 0;
    }

九.NEFU-874  
相约摩洛哥  
Time Limit:1000ms  
Memory Limit:65536K  
作为本次大赛的举办方负责人阿焜和阿祥被分配给了一个重要的任务，就是在比赛中统计大家的排名。  
acm大赛排名规则（摘自百度百科）：  
最后的获胜者为正确解答题目最多且总用时最少的队伍。每道试题用时将从竞赛开始到试题解答被判定为正确为止，其间每一次提交运行结果被判错误的话将被加罚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队以总用时少而获胜。  
请你帮他俩完成这项任务吧！（保证没有成绩完全相同两支队伍）  
Input  
多组输入，每组一个正整数n（1<=n<=100000），代表有n个队伍参赛。接下来的n行，每行分别有一个字符串（只包含小写英文字母）作为队伍名，长度1<=len<=10;ABC三道题的ac时间（以分钟为单位），时间为-1表示该题没有ac。接下来又有n行，表示每道题的提交次数,用3个正整数表示。  
Output  
输出排行榜。n行，每行一个队伍的名字、解题数和总用时。  
Sample Input  
3  
team 30 10 20  
behappy 20 20 90  
newbee 15 16 17  
1 1 1  
1 1 10  
1 1 1  
Sample Output  
newbee 3 48  
team 3 60  
behappy 3 310

注意罚时的计算方法，以及排名的规则，变量有点多。

#include <bits/stdc++.h>
    using namespace std;
    struct stu
    {
        
        char c[100];
        int a;
        int b;
        int k;
        int csa;       //a题花费的时间
        int csb;        //b题花费的时间
        int csc;
        int csz;
        int cs;           //做出来的总共题目数量
        int cost;
        int right;
    };
    bool cmp(stu a,stu b)
    {
        
        if(a.cs!=b.cs)
        {
        
            return a.cs>b.cs;
        }
        else
        {
        
            return a.cost<b.cost;
        }
    }
    int main()
    {
        
        int n;
        while(cin>>n)
        {
        
            struct stu p[n];
            for(int i=0;i<n;i++)
            {
        
                cin>>p[i].c>>p[i].a>>p[i].b>>p[i].k;
                p[i].cs=3;
                if(p[i].a==-1)
                {
        
                    p[i].cs--;
                }
                if(p[i].b==-1)
                {
        
                    p[i].cs--;
                }
                if(p[i].k==-1)
                {
        
                    p[i].cs--;
                }
            }
            for(int q=0;q<n;q++)
            {
        
                p[q].cost=0;
                p[q].csz=0;
                cin>>p[q].csa>>p[q].csb>>p[q].csc;
                if(p[q].a!=-1)
                {
        
                   p[q].csz+=(p[q].csa-1);
                }
                if(p[q].b!=-1)
                {
        
                    p[q].csz+=(p[q].csb-1);
                }
                if(p[q].k!=-1)
                {
        
                    p[q].csz+=(p[q].csc-1);
                }
                p[q].cost=p[q].csz*20;
                if(p[q].a!=-1)
                {
        
                    p[q].cost+=p[q].a;
                }
                if(p[q].b!=-1)
                {
        
                    p[q].cost+=p[q].b;
                }
                if(p[q].k!=-1)
                {
        
                    p[q].cost+=p[q].k;
                }
            }
            sort(p,p+n,cmp);
            for(int j=0;j<n;j++)
            {
        
                cout<<p[j].c<<" "<<p[j].cs<<" "<<p[j].cost<<endl;
            }
        }
        return 0;
    }