Party Games-白红宇

Party Games

阅读量：6324 次

发布时间：2019-06-22

本文共 2455 字，大约阅读时间需要 8 分钟。

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

FRED

SAM

JOE

MARGARET

FRED

FREDDIE

JOSEPHINE

JERRY

Sample Input

FRED

SAM

JOE

MARGARET

FRED

FREDDIE

JOSEPHINE

JERRY

2012 Southeast USA Regional Programming Contest

题意：

串A，串B ，寻找串C ，s.t. A<=C<B 且满足C.length最小。

也就是2个指针的应用，值得一做的试题。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 #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