Uva1610 利用暴力法避开细节处理

一、题意

给n个字符串（n<=1000，n为偶数），要你找一个最短的字符串S，使得恰好有一半的串小于等于S，另一半大于S。
如有多解，输出字典序最小的解。

二、解析

第一步操作是显然的：排序这n个字符串，然后取出最中间的两个，假设为a，b。
下面就是要少一个字符串res使得res>=a，res<b。

网上有许多做法是通过各种if语句进行判断，由于细节很多容易出错，我这里介绍另一种稍微暴力一些的方法。

即逐位增加res串，然后维护res串使其不断向<=a和>b的结果上靠拢。最终就能得到答案串。具体见代码。

三、代码

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int maxn = 1000 + 5;
int n;
string a[maxn];

string solve(const string& a, const string& b) {
    string res;
    int cnt = 0;
    while(res < a || res >= b) {
        res += 'A';
        while(res < a && res[cnt] != 'Z') res[cnt] ++;
        while(res >= b) res[cnt] --;
        cnt ++;
    }
    return res;
}

int main() {
    while(cin >> n && n) {
        for(int i = 0; i < n; i ++) cin >> a[i];
        sort(a, a + n);
        cout << solve(a[n / 2 - 1], a[n / 2]) << endl;
    }
}

四、归纳

• 又是细节繁多的题目可以考虑一下暴力维护的方法。