校赛1005

 

Problem E

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0

 

Problem Description
You've been invited to a party. The host wants to divide the guests into 2 teams for party games, with exactly the same number of guests on each team. She wants to be able to tell which guest is on which team as she greets them as they arrive, and as easily as possible, without having to take the time to look up each guest's name on a list. Being a good computer scientist, you have an idea: give her a single string, and all she has to do is determine whether the guest's name is alphabetically less than or greater than that string.
Given the unique names of n party guests (n is even), find the shortest possible string S such that exactly half the names are less than or equal to S, and exactly half are greater than S. If there’s more than one string of the shortest length, output the one that comes first alphabetically.
 


 

Input
There will be multiple test cases in the input. Each test case will begin with an even integer n (2≤n≤1,000) on its own line. On the next n lines will be names, one per line. Each name will be a single word consisting only of capital letters, and will be at least one letter and no longer than 30 letters. All of the names in a test case will be unique. The input will end with a 0 on its own line.
 


 

Output
For each case, output the alphabetically first of all of the shortest possible strings that your host could use to separate her guests. Output this string using all upper case letters. Do not output any spaces. Do not put a blank line between outputs.
 


 

Sample Input
4
FRED
SAM
JOE
MARGARET
2 FRED FREDDIE
2
JOSEPHINE
JERRY
0
 
 
Sample Output
K
FRED
JF
 


 


Statistic | Submit | Clarifications | Back


 

今天校赛被这题坑了2个小时,,最后悲剧的没做出来,还是太慌张了,大脑紊乱。。比赛一结束就思路清晰了。。
下面放上代码,不知对错。。

#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	getchar();
	while(n!=0)
	{
		string s[1010];
		int i;
		for(i=1;i<=n;i++)
			cin>>s[i];
		sort(s+1,s+1+n);
		int small=n/2;
		int large=n/2+1;
		int len1=s[small].length();
		int len2=s[large].length();
		int cnt=0;
		char ans[1010];
		if(len1<len2)
		{
			for(i=0;i<=len1-1;i++)
			{
				if(s[small][i]==s[large][i])
					ans[cnt++]=s[small][i];
				else
				{
					ans[cnt++]=s[small][i]+1;
					break;
				}
			}
			ans[cnt++]='\0';
		}
		else if(len1>len2)
		{
			for(i=0;i<=len2-1;i++)
			{
				if(s[small][i]==s[large][i])
				{
					ans[cnt++]=s[small][i];
				}
				else if(i!=len2-1 || (i==len2-1 && s[small][i]<s[large][i]-1))
				{
					ans[cnt++]=s[small][i]+1;
					break;
				
				}
				else
				{
					ans[cnt++]=s[small][i];
					for(int j=i+1;j<=len1-1;j++)
					{
						if(s[small][j]=='Z')
							ans[cnt++]=s[small][j];
						else
						{
							ans[cnt++]=s[small][j]+1;
							break;
						}
					}
					break;
				}
			
			}
			ans[cnt++]='\0';
		}
		else if(len1==len2)
		{
			for(i=0;i<=len1-1;i++)
			{
				if(s[small][i]==s[large][i])
				{
					ans[cnt++]=s[small][i];
				}
				else if(i!=len1-1 || (i==len1-1 && s[small][i]<s[large][i]-1))
				{
					ans[cnt++]=s[small][i]+1;
				}
				else
				{
					ans[cnt++]=s[small][i];
					break;
				}
			}
			ans[cnt++]='\0';
		}
		printf("%s\n",ans);
	
		scanf("%d",&n);
		getchar();
	}
//system("pause");
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>