UVa 1610 - Party Games(细节处理)

输入一个含有偶数个串的集合,求一个字符串s0,使集合中一半的串大于s0,另一半小于等于s0,多解输出字典序最小的解。只需将s与中间两个串比较即可。

新串s0从空串开始,每次循环加上一个s1中对应位置的字符。只要满足条件就跳出循环,输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
int main(){
int n;
while(cin>>n&&n){
int k=n/2;
string s0,s1,s2,temp;
vector<string>words;
while(n--){
cin>>s1;
words.push_back(s1);
}
sort(words.begin(),words.end());
s1=words[k-1],s2=words[k];//找到中间串。
int cur=0;
while(1){
for(int i=0;i<26;i++){
temp=s0;
temp+=i+'A';
if(temp>=s1&&temp<s2)
goto END;
}
s0+=s1[cur++];
}
END:
cout<<temp<<endl;
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。