Party Games
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 Input
4
FRED
SAM
JOE
MARGARET
2
FRED
FREDDIE
2
JOSEPHINE
JERRY
0
2012 Southeast USA Regional Programming Contest
http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11397
题意：
串A，串B ，寻找串C ，s.t. A<=C<B 且满足C.length最小 。
也就是2个指针的应用，值得一做的试题。
#include <iostream> #include <stdio.h> #include <queue> #include <stdio.h> #include <string.h> #include <vector> #include <queue> #include <set> #include <algorithm> #include <map> #include <stack> #include <math.h> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std ; typedef long long LL ; const int N_size=32 ; struct Stu{ char name[N_size] ; friend bool operator < (Stu A ,Stu B){ return strcmp(A.name,B.name)<0 ; } }; Stu stu[1008] ; int N ; string gao(){ string A ,B ; string ans ; char ans_char[N_size] ; A=string(stu[N/2].name) ; B=string(stu[N/2+1].name) ; int i=0 ; int j=0 ; while(i<A.length()&&j<B.length()){ if(A[i]==B[j]){ ans_char[i]=A[i] ; i++ ; j++ ; } else{ ans_char[i]=A[i] ; ans_char[i+1]=' ' ; ans=string(ans_char) ; if(A<=ans&&ans<B) return ans ; if(A[i]<'Z'){ ans_char[i]=A[i]+1 ; ans_char[i+1]=' ' ; ans=string(ans_char) ; if(A<=ans&&ans<B) return ans ; } ans_char[i]=A[i] ; i++ ; j++ ; } } if(i==A.length()) return A ; for(j=i;j<A.length();j++){ ans_char[j]=A[j] ; ans_char[j+1]=' ' ; ans=string(ans_char) ; if(A<=ans&&ans<B) return ans ; if(A[j]<'Z'){ ans_char[j]=A[j]+1 ; ans_char[j+1]=' ' ; ans=string(ans_char) ; if(A<=ans&&ans<B) return ans ; } ans_char[j]=A[j] ; } } int main(){ while(scanf("%d",&N)&&N){ for(int i=1;i<=N;i++) scanf("%s",stu[i].name) ; sort(stu+1,stu+1+N) ; cout<<gao()<<endl ; } return 0 ; }