2017年7月17日 星期一

[UVA] 1610 - Party Games

題目連結
題目說明:
給偶數個字串,要輸出一個最短字串 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;
}

沒有留言:

張貼留言