投稿
  1. 首页
  2. 随笔

acm寒假训练第二周总结

厦大选课系统 • 2022-12-17 • 随笔 • 阅读 36

acm寒假训练第二周总结,第1张

acm寒假训练第二周总结 排序

目录

一、实例：

1.P1271 【深基9.例1】选举学生会

2.P1177 【模板】快速排序

3.P1923 【深基9.例4】求第 k 小的数

4.P1059 [NOIP2006 普及组] 明明的随机数

5.P1093 [NOIP2007 普及组] 奖学金

6.P1781 宇宙总统

7.P2676 [USACO07DEC]Bookshelf B

8.P1116 车厢重组

9.P1152 欢乐的跳

11.P5143 攀爬者

12.P1104 生日

13.P1012 [NOIP1998 提高组] 拼数

二、总结

一、实例： 1.P1271 【深基9.例1】选举学生会

P1271 【深基9.例1】选举学生会 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这道题就是将m张选票从小到大进行排序，由于数量比较大，为了不超时我们使用快排。

#include
int a[10000000];
int quick_sort(int *a,int low,int high)
{
    int i=low,j=high;
    int mid=(i+j)/2;
    int temp1;
    if(a[j]a[i])
    {
        temp1=a[i];
        a[i]=a[mid];
        a[mid]=temp1;
    }
    int temp=a[i];
    while(i=temp)
        {
            j--;
        }
        a[i]=a[j];
        while(ilow)
        quick_sort(a,low,i-1);
    if(i+1 
2.P1177 【模板】快速排序 

P1177 【模板】快速排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 

#include
int a[10000000];
int quick_sort(int low,int high)
{
    int i=low,j=high;
    int mid=(i+j)/2;
    int temp1;
    if(a[j]a[i])
    {
        temp1=a[i];
        a[i]=a[mid];
        a[mid]=temp1;
    }
    int temp=a[i];
    while(i=temp)
        {
            j--;
        }
        a[i]=a[j];
        while(ilow)
        quick_sort(low,i-1);
    if(i+1 
3.P1923 【深基9.例4】求第 k 小的数 

P1923 【深基9.例4】求第 k 小的数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 

这道题就是将n个数字排好序，输出第k小的数。
 

#include
int a[10000000];
int quick_sort(int *a,int low,int high)
{
    int i=low,j=high;
    int mid=(i+j)/2;
    int temp1;
    if(a[j]a[i])
    {
        temp1=a[i];
        a[i]=a[mid];
        a[mid]=temp1;
    }
    int temp=a[i];
    while(i=temp)
        {
            j--;
        }
        a[i]=a[j];
        while(ilow)
        quick_sort(a,low,i-1);
    if(i+1 
4.P1059 [NOIP2006 普及组] 明明的随机数 

P1059 [NOIP2006 普及组] 明明的随机数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 

先将数组中的重复数字进行删除，每删除一个就将后面的覆盖前面的，然后再进行排序。
 

#include 
int main(void)
{
    int n,a[100],i,j,k,temp;
    scanf("%d",&n);
    for(i=0;ia[j+1])
            {
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
    printf("%dn",n);
    for(i=0;i 
5.P1093 [NOIP2007 普及组] 奖学金 

P1093 [NOIP2007 普及组] 奖学金 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 

结构体排序，先将学号和总成绩储存在结构体数组中，然后先按照总成绩排序，如果总成绩相同的，比较语文成绩，如果语文成绩也相同，最后比较学号，学号小的排在前面。
 

#include
struct student
{
    int C;
    int M;
    int E;
    int sum;
    int num;
}stu[300];
int main(void)
{
    struct student temp;
    int n,i,j;
    scanf("%d",&n);
    for(i=0;istu[j].num)
                    {
                        temp=stu[i];
                        stu[i]=stu[j];
                        stu[j]=temp;
                    }
                }
            }
        }
    }
    for(i=0;i<5;i++)
        printf("%d %dn",stu[i].num,stu[i].sum);
    return 0;
}
 
6.P1781 宇宙总统 

P1781 宇宙总统 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 

将输入的数字储存在数组中，计算出每个字符串的长度，将最长的放在最前面，然后在比较最长的有没有相同长度的，然后比较大小，将最大的放在最前面，最后与之前复制的数组比较，输出号数，然后输出票数。
 

#include
#include
struct candidate
{
    char a[100];
    int l;//储存各个字符串的长度
}cand[20];
int main(void)
{
    struct candidate temp;
    int n,i,j,t;
    char b[20][100];
    scanf("%d",&n);
    for(i=0;i 
7.P2676 [USACO07DEC]Bookshelf B 

P2676 [USACO07DEC]Bookshelf B - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 

将牛按照身高从大到小进行排序，依次累加，直到高度大于等于书架顶部，输出最少奶牛的数量。
 

#include
#include
int main(void)
{
    int n,b,t,s=0,k=0;//s记录牛的身高，k记录牛的数量
    int a[20000];
    int i,j;
    scanf("%d%d",&n,&b);
    for(i=0;i=0&&a[j]>t;j--)//如果前面的大于后面的
        {
            a[j+1]=a[j];//前面的赋值给后面的
        }
        a[j+1]=t;//因为j--，所以是j+1,将原来后面的赋值给前面的
    }
    for(i=n-1;i>=0;i--)
    {
        s+=a[i];
        k++;
        if(s>=b)
        {
             printf("%d",k);
             return 0;
        }
    }
    return 0;
}

 
8.P1116 车厢重组 

P1116 车厢重组 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 

这道题就是将车厢按车厢号从小到大排列，最少用多少步就能将车厢排序，每进行一次交换，就将k++,z最后输出k。
 

#include
int main(void)
{
    int n,a[10000],k=0;
    int i,j,t;
    scanf("%d",&n);
    for(i=0;ia[j+1])
            {
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
                k++;
            }
        }
    }
    printf("%d",k);
    return 0;
}
 
9.P1152 欢乐的跳 

P1152 欢乐的跳 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 

将n个元素的整数数组两个连续元素之间差的绝对值储存到另一个数组中，从小到大进行排序，如果包括了1到n-1之间的所有整数，则输出Jolly，否则输出Not jolly。
 

#include
#include
int main(void)
{
    int a[1000],b[1000];
    int n,i,j,t;
    scanf("%d",&n);
    for(i=0;ib[j])
            {
                t=b[i];
                b[i]=b[j];
                b[j]=t;
            }
        }
    }
    for(i=0;i 

10.P1068 [NOIP2009 普及组] 分数线划定
 

P1068 [NOIP2009 普及组] 分数线划定 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 

面试分数线为排名第p=m  150%（向下取整）名的选手的分数，按笔试成绩排名从大到小进行排序，如果第p名成绩与后面的相同，则将p++,最后如果成绩相同，则按照报名号进行排序。
 

#include
#include
struct people
{
    int num;
    int sorce;
}stu[5000];
int main(void)
{
    struct people temp;
    int n,p,i,j,m;
    scanf("%d%d",&n,&m);
    for(i=0;istu[j].num)
                {
                    temp=stu[i];
                    stu[i]=stu[j];
                    stu[j]=temp;
                }
            }
        }
    }
    printf("%d %dn",stu[p-1].sorce,p);
    for(i=0;i 
11.P5143 攀爬者 

P5143 攀爬者 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 

#include
#include
struct coord//坐标
{
    int x;
    int y;
    int z;
}point[50000];
int quick_sort(int low,int high)
{
    int t;
    int i=low,j=high;
    int temp=point[i].z;
    while(i=temp)
        {
            j--;
        }
        point[i].z=point[j].z;
        t=point[i].x;
        point[i].x=point[j].x;
        point[j].x=t;
        t=point[i].y;
        point[i].y=point[j].y;
        point[j].y=t;
        while(ilow)
        quick_sort(low,i-1);
    if(i+1 
12.P1104 生日 

P1104 生日 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 

#include
#include
struct student
{
    char name[20];
    int year;
    int month;
    int day;
    int in;//输入顺序
}stu[100];
int main(void)
{
    struct student temp;
    int i,j,n;
    int t;//
    scanf("%d",&n);
    for(i=0;istu[j].year)
            {
                temp=stu[i];
                stu[i]=stu[j];
                stu[j]=temp;
            }
        }
    }
    //比较月
    for(i=0;istu[j].month)
                {
                    temp=stu[i];
                    stu[i]=stu[j];
                    stu[j]=temp;
                }
            }
        }
    }
    //比较日
    for(i=0;istu[j].day)
                    {
                        temp=stu[i];
                        stu[i]=stu[j];
                        stu[j]=temp;
                    }
                }
            }
        }
    }
    for(i=0;i 
13.P1012 [NOIP1998 提高组] 拼数 

P1012 [NOIP1998 提高组] 拼数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 

这道题直接用字典序排序最后一个会WA，如果输入是321 32，按照字典序排序是32132，但是这样没有32321大，所以需要将a[i]+a[j]和a[j]+a[i]进行比较。
 

#include
#include
int main(void)
{
    int n,i,j;
    char a[20][100],t1[100],t2[100];
    char temp[100];
    scanf("%d",&n);
    for(i=0;i 
二、总结 

1.经过这一周的练习排序，可以感觉到自己又有了一些提升，但是面对提高组及以上的题还是有些吃力，但是有了一些进步。
 

2.这一周就是掌握了几种排序的模板，可以在不同的问题下，应用最适合的排序方法。
 

3.有的题使用普通快排也会出现超时，所以我们需要对快排做出一些优化，比如选择基准的时候进行三点取中的方法。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5710431.html
赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
厦大选课系统 厦大选课系统 一级用户组
0 0
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表（0条）

保存