暑假集训之——sort+结构体练习

╰半橙微兮° 2022-05-19 04:22 143阅读 0赞

虽然有很多题以前有做过，可这次做还是WA了好几发，有些东西看来还是没有掌握透彻。

# A - A #

[来源：ＨＤＵ１２３４][Link 1]

每天第一个到机房的人要把门打开，最后一个离开的人要把门关好。现有一堆杂乱的机房签  
到、签离记录，请根据记录找出当天开门和关门的人。

Input

测试输入的第一行给出记录的总天数N ( > 0 )。下面列出了N天的记录。  
每天的记录在第一行给出记录的条目数M ( > 0 )，下面是M行，每行的格式为  
  
证件号码 签到时间 签离时间  
  
其中时间按“小时:分钟:秒钟”（各占2位）给出，证件号码是长度不超过15的字符串。

Output

对每一天的记录输出1行，即当天开门和关门人的证件号码，中间用1空格分隔。  
注意：在裁判的标准测试输入中，所有记录保证完整，每个人的签到时间在签离时间之前，  
且没有多人同时签到或者签离的情况。

Sample Input

3
    1
    ME3021112225321 00:00:00 23:59:59
    2
    EE301218 08:05:35 20:56:35
    MA301134 12:35:45 21:40:42
    3
    CS301111 15:30:28 17:00:10
    SC3021234 08:00:00 11:25:25
    CS301133 21:45:00 21:58:40

Sample Output

ME3021112225321 ME3021112225321
    EE301218 MA301134
    SC3021234 CS301133

思路：**将时间都处理为以秒为单位的，开门人来的时间是最早的，关门人走的时间是最晚的，对于每一个人来说，都有与之对应的到达时间和离开时间。两个排序可以找到**

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    struct node{
    	char name[100];
    	int sh,sm,ss,eh,em,es;
    	int st,et;
    }a[10000];
    bool cmp1(node x,node y)
    {
    	return x.st<y.st;
    }
    bool cmp2(node x,node y)
    {
    	return x.et>y.et;
    }
    int main()
    {
    	int n,m;
    	scanf("%d",&m);
    	while(m--)
    	{
    		scanf("%d",&n);
    		for(int i=0;i<n;i++)
    		{
    			scanf("%s %d:%d:%d %d:%d:%d",a[i].name,&a[i].sh,&a[i].sm,&a[i].ss,&a[i].eh,&a[i].em,&a[i].es);
    			a[i].st=a[i].sh*3600+a[i].sm*60+a[i].ss;
    			a[i].et=a[i].eh*3600+a[i].em*60+a[i].es;
    		}
    		sort(a,a+n,cmp1);
    		printf("%s",a[0].name);
    		sort(a,a+n,cmp2);
    		printf(" %s\n",a[0].name);
    		
    	}
    	return 0;
    }

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

# B - B #

Excel可以对一组纪录按任意指定列排序。现请你编写程序实现类似功能。

Input

测试输入包含若干测试用例。每个测试用例的第1行包含两个整数 N (<=100000) 和 C，其中 N 是纪录的条数，C 是指定排序的列号。以下有 N  
行，每行包含一条学生纪录。每条学生纪录由学号（6位数字，同组测试中没有重复的学号）、姓名（不超过8位且不包含空格的字符串）、成绩（闭区间\[0, 100\]内的整数）组成，每个项目间用1个空格隔开。当读到 N=0 时，全部输入结束，相应的结果不要输出。

Output

对每个测试用例，首先输出1行“Case i:”，其中 i 是测试用例的编号（从1开始）。随后在 N 行中输出按要求排序后的结果，即：当 C=1 时，按学号递增排序；当 C=2时，按姓名的非递减字典序排序；当 C=3  
时，按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时，则按他们的学号递增排序。

Sample Input

3 1
    000007 James 85
    000010 Amy 90
    000001 Zoe 60
    4 2
    000007 James 85
    000010 Amy 90
    000001 Zoe 60
    000002 James 98
    4 3
    000007 James 85
    000010 Amy 90
    000001 Zoe 60
    000002 James 90
    0 0

Sample Output

Case 1:
    000001 Zoe 60
    000007 James 85
    000010 Amy 90
    Case 2:
    000010 Amy 90
    000002 James 98
    000007 James 85
    000001 Zoe 60
    Case 3:
    000001 Zoe 60
    000007 James 85
    000002 James 90
    000010 Amy 90

**姓名或者成绩相同的时候按学号递增排序，注意一下这点就好了**

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int maxn=100000+9;
    struct node{
    	int id,score;
    	char name[10];
    }a[maxn];
    
    bool cmp1(node x,node y)
    {
    	return x.id<y.id;
    }
    bool cmp2(node x,node y)
    {
    	return strcmp(x.name,y.name)==0?x.id<y.id:strcmp(x.name,y.name)<0;
    }
    bool cmp3(node x,node y)
    {
    	return x.score==y.score?x.id<y.id:x.score<y.score;
    }
    
    int main()
    {
    	int n,c;
    	int t=0;
    	while(~scanf("%d %d",&n,&c)&&n)
    	{
    		for(int i=0;i<n;i++)
    			cin>>a[i].id>>a[i].name>>a[i].score;
    		switch (c)
    		{
    			case 1:sort(a,a+n,cmp1);break;
    			case 2:sort(a,a+n,cmp2);break;
    			case 3:sort(a,a+n,cmp3);break;
    		}
    		printf("Case %d:\n",++t);
    		for(int i=0;i<n;i++)
    		printf("%06d %s %d\n",a[i].id,a[i].name,a[i].score);
    	}
    	return 0;
    }

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

# C - C #

还记得Gardon给小希布置的那个作业么？（上次比赛的1005）其实小希已经找回了原来的那张数表，现在她想确认一下她的答案是否正确，但是整个的答案是很庞大的表，小希只想让你把答案中最大的M个数告诉她就可以了。  
给定一个包含N(N<=3000)个正整数的序列，每个数不超过5000，对它们两两相加得到的N\*(N-1)/2个和，求出其中前M大的数(M<=1000)并按从大到小的顺序排列。

Input

输入可能包含多组数据，其中每组数据包括两行：  
第一行两个数N和M，  
第二行N个数，表示该序列。

Output

对于输入的每组数据，输出M个数，表示结果。输出应当按照从大到小的顺序排列。

Sample Input

4 4
    1 2 3 4
    4 5
    5 3 6 4

Sample Output

7 6 5 5
    11 10 9 9 8

**暴力出奇迹。**

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int maxn=3002;
    int a[maxn];
    int b[maxn*maxn];
    
    bool cmp(int x,int y)
    {
    	return x>y;
    }
    
    int main()
    {
    	int n,m;
    	while(~scanf("%d %d",&n,&m))
    	{
    		for(int i=0;i<n;i++)
    			scanf("%d",&a[i]);
    		int z=0;
    		for(int i=0;i<n;i++)
    			for(int j=i+1;j<n;j++)
    				b[z++]=a[i]+a[j];
    		sort(b,b+z,cmp);
    		for(int i=0;i<m;i++)
    		{
    			if(i)	printf(" ");
    			printf("%d",b[i]);
    		}
    		printf("\n");
    	}
    	return 0;
    }

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

# D - D #

读入N名学生的成绩，将获得某一给定分数的学生人数输出。

Input

测试输入包含若干测试用例，每个测试用例的格式为  
  
  
第1行：N  
第2行：N名学生的成绩，相邻两数字用一个空格间隔。  
第3行：给定分数  
  
当读到N=0时输入结束。其中N不超过1000，成绩分数为（包含）0到100之间的一个整数。

Output

对每个测试用例，将获得给定分数的学生人数输出。

Sample Input

3
    80 60 90
    60
    2
    85 66
    0
    5
    60 75 90 55 75
    75
    0

Sample Output

1
    0
    2
    
    
            
      
    Huge input, scanf is recommended.

**数量比较小的话用桶排序比较方便**

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int score[105];
    int main()
    {
    	int n,m;	int x;
    	while(~scanf("%d",&n)&&n)
    	{
    		memset(score,0,sizeof(score));
    		for(int i=0;i<n;i++)
    		{
    			scanf("%d",&x);
    			score[x]++;
    		}
    		scanf("%d",&m);
    		printf("%d\n",score[m]);
    	 } 
    	return 0;
    }

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

# E - E #

大家都知道，快速排序是不稳定的排序方法。  
如果对于数组中出现的任意a\[i\],a\[j\](i<j),其中a\[i\]==a\[j\]，在进行排序以后a\[i\]一定出现在a\[j\]之前，则认为该排序是稳定的。  
  
某高校招生办得到一份成绩列表，上面记录了考生名字和考生成绩。并且对其使用了某排序算法按成绩进行递减排序。现在请你判断一下该排序算法是否正确，如果正确的话，则判断该排序算法是否为稳定的。

Input

本题目包含多组输入，请处理到文件结束。  
对于每组数据，第一行有一个正整数N(0<N<300)，代表成绩列表中的考生数目。  
接下来有N行，每一行有一个字符串代表考生名字(长度不超过50，仅包含'a'~'z'),和一个整数代表考生分数(小于500)。其中名字和成绩用一个空格隔开。  
再接下来又有N行，是上述列表经过某排序算法以后生成的一个序列。格式同上。

Output

对于每组数据，如果算法是正确并且稳定的，就在一行里面输出"Right"。如果算法是正确的但不是稳定的，就在一行里面输出"Not Stable"，并且在下面输出正确稳定排序的列表，格式同输入。如果该算法是错误的，就在一行里面输出"Error",并且在下面输出正确稳定排序的列表，格式同输入。  
  
注意，本题目不考虑该排序算法是错误的，但结果是正确的这样的意外情况。

Sample Input

3
    aa 10
    bb 10
    cc 20
    cc 20
    bb 10
    aa 10
    3
    aa 10
    bb 10
    cc 20
    cc 20
    aa 10
    bb 10
    3
    aa 10
    bb 10
    cc 20
    aa 10
    bb 10
    cc 20

Sample Output

Not Stable
    cc 20
    aa 10
    bb 10
    Right
    Error
    cc 20
    aa 10
    bb 10

**ＷＡ了好几次，因为没有注意题意。。。**

**这道题要注意如果成绩相同的话，姓名是按照输入的顺序排列的，这点比较坑**

**需要记录下输入顺序**

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int maxn=300+9;
    struct node{
    	char name[55];
    	int score,m;
    }a[maxn];
    
    bool cmp(node x,node y)
    {
    	return x.score==y.score?x.m<y.m:x.score>y.score;//成绩相同的话按照输入顺序从小到大排列 
    }
    
    int main()
    {
    	int n;
    	node b[maxn];
    	while(~scanf("%d",&n))
    	{
    		for(int i=0;i<n;i++)
    		{
    			cin>>a[i].name>>a[i].score;
    			a[i].m=i;//记录输入的顺序 
    		}
    		for(int i=0;i<n;i++)
    			cin>>b[i].name>>b[i].score;
    		sort(a,a+n,cmp);
    		int x=0,y=0;
    		for(int i=0;i<n;i++)
    			if(a[i].score!=b[i].score)
    			{
    				y=1;//Error
    				break;
    			 } 
    		for(int i=0;i<n;i++)
    			if(strcmp(a[i].name,b[i].name)!=0)	
    			{
    				x=1;//Not Stable
    				break;
    			}
    		if(x==0&&y==0)	
    		{
    			printf("Right\n");
    			continue;
    		}
    		if(y==1)
    		{
    			printf("Error\n");
    			for(int i=0;i<n;i++)
    				printf("%s %d\n",a[i].name,a[i].score);
    			continue;
    		}
    		if(x==1)
    		{
    			printf("Not Stable\n");
    			for(int i=0;i<n;i++)
    				printf("%s %d\n",a[i].name,a[i].score);
    		}
    	}
    	return 0;
    }

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

# F - F #

“Point, point, life of student!”  
This is a ballad（歌谣）well known in colleges, and you must care about your score in this exam too. How many points can you get? Now, I told you the rules which are used in this course.  
There are 5 problems in this final exam. And I will give you 100 points if you can solve all 5 problems; of course, it is fairly difficulty for many of you. If you can solve 4 problems, you can also get a high score 95 or 90 (you can get the former(前者) only when your rank is in the first half of all students who solve 4 problems). Analogically（以此类推）, you can get 85、80、75、70、65、60. But you will not pass this exam if you solve nothing problem, and I will mark your score with 50.  
Note, only 1 student will get the score 95 when 3 students have solved 4 problems.  
I wish you all can pass the exam!  
Come on!

Input

Input contains multiple test cases. Each test case contains an integer N (1<=N<=100, the number of students) in a line first, and then N lines follow. Each line contains P (0<=P<=5 number of problems that have been solved) and T（consumed time）. You can assume that all data are different when 0<p.  
A test case starting with a negative integer terminates the input and this test case should not to be processed.

Output

Output the scores of N students in N lines for each case, and there is a blank line after each case.

Sample Input

4
    5 06:30:17
    4 07:31:27
    4 08:12:12
    4 05:23:13
    1
    5 06:30:17
    -1

Sample Output

100
    90
    90
    95
    
    100

有五道题，全做对得１００分，做对０道得５０（交白卷还给分？）

做对４道可以得９５　ｏｒ９０

做对３道可以得８５　ｏｒ８０

做对２道可以得７５　ｏｒ７０

做对１道可以得６５　ｏｒ６０

在做对相同题目的人中，排名靠前的一半比排名靠后的多得５分（注意，３个人都做对４道题的话只有一个人能够得到９５分）

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    struct node{
    	int score,problems,num,t,h,m,s;
    }a[105];
    
    bool cmp1(node x,node y)
    {
    	return x.problems==y.problems?x.t<y.t:x.problems<y.problems;//按成绩从大到小排列，成绩相同按做题时间从小到大排列 
    }
    bool cmp2(node x,node y)
    {
    	return x.num<y.num;
    }
    int main()
    {
    	int n;
    	while(~scanf("%d",&n)&&(n>0))
    	{
    		for(int i=0;i<n;i++)
    		{
    			scanf("%d %d:%d:%d",&a[i].problems,&a[i].h,&a[i].m,&a[i].s);
    			a[i].num=i;
    			a[i].t=3600*a[i].h+60*a[i].m+a[i].s;
    			if(a[i].problems==5)	a[i].score=100;
    			if(a[i].problems==0)	a[i].score=50;
    		}
    		sort(a,a+n,cmp1);
    		int two=0;
    		int three=0;
    		int four=0;
    		int one=0;
    		for(int i=0;i<n;i++)
    		{
    			if(a[i].problems==4) four++;
    			if(a[i].problems==3) three++;
    			if(a[i].problems==2) two++;
    			if(a[i].problems==1) one++;
    		}
    //		printf("\n\nfour:%d\n\n",four);
    		int z=four/2;
    		int k=0;
    		for(int i=0;i<n;i++)
    		{
    			if(a[i].problems==4)
    			{
    				if(k<z)	a[i].score=95;
    				else		a[i].score=90;
    				k++;
    			}
    		}
    	 	z=three/2;
    		k=0;
    		for(int i=0;i<n;i++)
    		{
    			if(a[i].problems==3)
    			{
    				if(k<z)	a[i].score=85;
    				else		a[i].score=80;
    				k++;
    			}
    		}
    		z=two/2;
    		k=0;
    		for(int i=0;i<n;i++)
    		{
    			if(a[i].problems==2)
    			{
    				if(k<z)	a[i].score=75;
    				else		a[i].score=70;
    				k++;
    			}
    		}
    		z=one/2;
    		k=0;
    		for(int i=0;i<n;i++)
    		{
    			if(a[i].problems==1)
    			{
    				if(k<z)	a[i].score=65;
    				else		a[i].score=60;
    				k++;
    			}
    		}
    		sort(a,a+n,cmp2);
    		for(int i=0;i<n;i++)
    			printf("%d\n",a[i].score);
    		printf("\n");
    	}
    	return 0;
    }

这里是很久之前的代码，思路基本是一样的：

#include<stdio.h> 
    #include<string.h>
    #include<algorithm>
    using namespace std;
    struct node{
        int t,h,m,s;
        int first;
        int grade,score;
    }a[101];
    int cmp1(node x,node y)
    {
        return x.grade!=y.grade?x.grade>y.grade:x.t<y.t;
    }
    int cmp2(node x,node y)
    {
        return x.first<y.first;
    }
    int main() 
    {
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            if(n<0)    break;
            for(int i=0;i<n;i++)
            {
                scanf("%d %d:%d:%d",&a[i].grade,&a[i].h,&a[i].m,&a[i].s);
                a[i].first=i;
                a[i].t=a[i].h*3600+a[i].m*60+a[i].s;
            }
            sort(a,a+n,cmp1);
            int g1=0,g2=0,g3=0,g4=0,c1,c2,c3,c4;
            for(int i=0;i<n;i++)
            {
                if(a[i].grade==5)    a[i].score=100;
                if(a[i].grade==4)    g4++; 
                if(a[i].grade==3)    g3++;
                if(a[i].grade==2)    g2++;
                if(a[i].grade==1)    g1++;
                if(a[i].grade==0)    a[i].score=50;
            }
            c4=g4/2;c3=g3/2;c2=g2/2;c1=g1/2;
            for(int i=0;i<n;i++)
            {
                if(c4>0&&a[i].grade==4)        {a[i].score=95;c4--;}    
                else if(a[i].grade==4)        a[i].score=90;
                if(c3>0&&a[i].grade==3)        {c3--;a[i].score=85;}    
                else if(a[i].grade==3)        a[i].score=80;
                if(c2>0&&a[i].grade==2)        {c2--;a[i].score=75;}    
                else if(a[i].grade==2)        a[i].score=70;
                if(c1>0&&a[i].grade==1)        {c1--;a[i].score=65;}    
                else if(a[i].grade==1)        a[i].score=60;
            }
            sort(a,a+n,cmp2);
            for(int i=0;i<n;i++)
            printf("%d\n",a[i].score);
            printf("\n");
        }
        return 0;
    }

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

# G - G #

Limak is a little polar bear. He has *n* balls, the *i*\-th ball has size *t**i*.

Limak wants to give one ball to each of his three friends. Giving gifts isn't easy — there are two rules Limak must obey to make friends happy:

*  No two friends can get balls of the same size.
 *  No two friends can get balls of sizes that differ by more than 2.

For example, Limak can choose balls with sizes 4, 5 and 3, or balls with sizes 90, 91 and 92. But he can't choose balls with sizes 5, 5 and 6 (two friends would get balls of the same size), and he can't choose balls with sizes 30, 31 and 33 (because sizes 30 and 33 differ by more than 2).

Your task is to check whether Limak can choose three balls that satisfy conditions above.

Input

The first line of the input contains one integer *n* (3 ≤ *n* ≤ 50) — the number of balls Limak has.

The second line contains *n* integers *t*1, *t*2, ..., *t**n* (1 ≤ *t**i* ≤ 1000) where *t**i* denotes the size of the *i*\-th ball.

Output

Print "YES" (without quotes) if Limak can choose three balls of distinct sizes, such that any two of them differ by no more than 2. Otherwise, print "NO" (without quotes).

Examples

Input

4
    18 55 16 17

Output

YES

Input

6
    40 41 43 44 44 44

Output

Input

8
    5 972 3 4 1 4 970 971

Output

YES

Note

In the first sample, there are 4 balls and Limak is able to choose three of them to satisfy the rules. He must must choose balls with sizes 18, 16 and 17.

In the second sample, there is no way to give gifts to three friends without breaking the rules.

In the third sample, there is even more than one way to choose balls:

1.  Choose balls with sizes 3, 4 and 5.
2.  Choose balls with sizes 972, 970, 971.

**思路：存在三个连续的数就输出ＹＥＳ否则ＮＯ**

#include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    
    int a[1005];
    int main()
    {
    	int n;
    	while(~scanf("%d",&n))
    	{
    		int x;
    		int k=0;
    		memset(a,0,sizeof(a));
    		for(int i=0;i<n;i++)
    		{
    			scanf("%d",&x);
    			a[x]++;
    		}
    		for(int i=1;i<1004;i++)
    			if(a[i]&&a[i+1]&&a[i+2])	
    			{
    				k=1;
    				break;
    			}
    		if(k)	printf("YES\n");
    		else	printf("NO\n");	
    	}
    	return 0;
    }

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

# H - H #

“今年暑假不AC？”  
“是的。”  
“那你干什么呢？”  
“看世界杯呀，笨蛋！”  
“@\#$%^&\*%...”  
  
确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。  
作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）

Input

输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti\_s,Ti\_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。

Output

对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。

Sample Input

12
    1 3
    3 4
    0 7
    3 8
    15 19
    15 20
    10 15
    8 18
    6 12
    5 10
    4 14
    2 9
    0

Sample Output

活动安排问题的模板题，按照结束时间早的顺序排序

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    struct node{
    	int st,et;
    }a[105]; 
    
    bool cmp(node x,node y)
    {
    	return x.et<y.et;
    }
    
    int main()
    {
    	int n;
    	while(~scanf("%d",&n)&&n)
    	{
    		for(int i=0;i<n;i++)
    			cin>>a[i].st>>a[i].et;
    		sort(a,a+n,cmp);
    		int z=a[0].et;
    		int ans=1;
    		for(int i=1;i<n;i++)
    			if(a[i].st>=z)
    			{
    				ans++;
    				z=a[i].et;
    			}
    		cout<<ans<<endl;
    	}
    	return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1234