mayoko’s diary

プロコンとかいろいろ。

SRM 506 div1 easy:SlimeXSlimesCity

SRM練習会に参加しました。結果はeasyをそこそこ早解きしただけです。medが面白い問題でした。

解法

それぞれの町iについて,最高で何人の住人が集まれるのかを考える。これは,町i以外の町について人口をソートして小さい順にiの町と比べた時,iの人口以下だったらiを町の名前にするようにマージすることができるのでそのようにマージする。
最終的に人口が最大の町よりも人口以上にできたらその町は答えの一つになりうる。

以下ソースコード

class SlimeXSlimesCity {
public:
    int merge(vector <int> population) {
        int n = population.size();
        vector<ll> p(n);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            p[i] = population[i];
        }
        for (int i = 0; i < n; i++) {
            vector<ll> q;
            for (int j = 0; j < n; j++) {
                if (j == i) continue;
                q.push_back(p[j]);
            }
            sort(q.begin(), q.end());
            ll ma = p[i];
            for (int j = 0; j < n-1; j++) {
                if (ma >= q[j]) {
                    ma += q[j];
                } else {
                    break;
                }
            }
            if (ma >= q[n-2]) {
                ans++;
            }
        }
        return ans;
    }
};