练54.3 竞选总统

解题思路

赢得一个州需floor(pop/2)+1人支持。先算每州最小成本并排序，再选成本最小的floor(N/2)+1州累加。

正确性说明

当选只需最少数量的州，各州成本独立；若选中成本高州而未选成本低州，替换能降低或保持费用，因此选最低的一半以上州最优。

易错点

必须超过半数州，超过半数选民，均为除2再加1。

复杂度

每组O(n log n)时间、O(n)空间。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n && n) {
        vector<int> a(n);
        for (int &x : a) {
            cin >> x;
            x = x / 2 + 1;
        }
        sort(a.begin(), a.end());
        int ans = 0;
        for (int i = 0; i < n / 2 + 1; i++)
            ans += a[i];
        cout << ans << "\n";
    }
    return 0;
}