首页 > 代码库 > UVa1610 Party Games (字符串)

UVa1610 Party Games (字符串)

链接:http://bak2.vjudge.net/problem/UVA-1610

分析:把n个字符串排序,拿中间两个字符串s1和s2比较即可。因为s1<s2,所以可以确定枚举len(s1)个长度肯定能找到解,然后从‘A‘开始枚举ans的每个位置,首先解要求最短,所以先循环找一个ans>=s1的解,注意保证ans[i]<=‘Z‘,判断是否满足条件,满足就是最优解则输出,否则将ans[i]置为s1[i],保证最优解的字典序最小,接着重复上述步骤枚举ans的下一个位置。

 

 

 1 #include <iostream> 2 #include <algorithm> 3 #include <string> 4 using namespace std; 5  6 const int maxn = 1000 + 5; 7  8 int main() { 9     int n;10     string s[maxn];11     while (cin >> n && n) {12         for (int i = 0; i < n; i++) cin >> s[i];13         sort(s, s+n);14         string s1 = s[(n>>1)-1], s2 = s[n>>1];15         int len = s1.size(), i = 0;16         string ans = "";17         ans += A;18         while (i < len) {19             while (ans[i] < Z && ans < s1) ++ans[i];20             if (ans >= s1 && ans < s2) break;21             ans[i] = s1[i];22             ans += A;23             i++;24         }25         cout << ans << endl;26     }27     return 0;28 }

 

UVa1610 Party Games (字符串)