題目連結
題目說明:
給偶數個字串,要輸出一個最短字串 S 可以滿足一半的字串小於等於S,一半大於S。
例如:
D A ABC AD
要輸出AC
==================================================
我的作法:
先將全部字串排序。
接著找到最中間兩個字串出來,分別為key1, key2,
對key1字串的每個字元從[0]開始試著+1,如果 < key2就直接break;
如果key1[i]是字元Z不能+1,所以就continue;看下一個字元。
==================================================
程式碼:
/* 題目: UVa 1610 - Party Games
* Language: C++
* Created on: 2017年07月17日
* Author: hanting
*/
#include <iostream>
#include <algorithm> // sort
using namespace std;
int main()
{
int strN;
while(cin >> strN && strN) // 必為偶數
{
string str[strN];
for(int i = 0; i < strN; i++)
{
cin >> str[i];
}
sort(str, str+strN);
string key1, key2; // 排序好的字串集合中最中間兩個字串
key1 = str[strN/2-1];
key2 = str[strN/2];
string ans = key1;
for(int i = 0; i < key1.size(); i++)
{
if(i == key1.size()-1)
{
ans = key1;
break;
}
string tmp = key1.substr(0, i+1);
if(tmp[i] == 'Z') continue;
tmp[i]++;
if(tmp < key2)
{
ans = tmp;
break;
}
}
cout << ans << endl;
}
return 0;
}
2017年7月17日 星期一
[UVA] 1610 - Party Games
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言