SRM 573 div1 easy: TeamContest

問題

TopCoder Statistics - Problem Statement

解法

貪欲法で解けます。

自チームに勝つためには, 相手はとりあえず強さが max の人はなるべく強いほうが良くて, それ以外の人はなるべく小さいほうが良いです。この規則でチームをどんどん作っていきましょう。

bool done[50];

class TeamContest {
public:
    int worstRank(vector <int> strength) {
        int n = strength.size();
        int score = max({strength[0], strength[1], strength[2]}) + min({strength[0], strength[1], strength[2]});
        vector<int> others;
        for (int i = 3; i < n; i++) others.push_back(strength[i]);
        sort(others.begin(), others.end());
        memset(done, false, sizeof(done));
        n = others.size();
        int ans = 1;
        for (int r = n-1; r >= 0; r--) {
            if (done[r]) continue;
            int l = 0;
            for (; l < r; l++) {
                if (!done[l] && others[r]+others[l] > score) break;
            }
            if (l==r) break;
            done[l] = done[r] = true;
            bool ok = false;
            for (int m = l+1; m < r; m++) if (!done[m]) {
                done[m] = true;
                ok = true;
                break;
            }
            if (!ok) break;
            ans++;
        }
        return ans;
    }
};