首页 > 代码库 > 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 (字符串)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。