AtCoder Regular Contest 046 C - 合コン大作戦

問題

arc046.contest.atcoder.jp

解法

貪欲にやっていきます。

男性を年収が低い順, 女性を希望年収が低い順に並べておきます。
で, 男性の年収が低い順に以下のことを調べます。

1. 今考えている男性を man とする。
2. man の年収で OK な女性を set に詰め込んでいく。
3. set に詰め込まれた女性の中で, man が希望する年収以上の女性のうち, 一番低い年収の女性を選ぶ。選べた場合は set からその女性を削除し, 答えに 1 を足す。

このようにすると, 損することなくカップルを選ぶことが出来ます。

あくまで解法の話をしているので人権問題は発生しないことに注意して下さい。

const int MAXN = 151001;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<pii> men(N), women(M);
    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        men[i] = pii(a, b);
    }
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        women[i] = pii(b, a);
    }
    sort(men.begin(), men.end());
    sort(women.begin(), women.end());
    map<int, int> mp;
    int cur = 0, ans = 0;
    for (int i = 0; i < N; i++) {
        while (cur < M && women[cur].first <= men[i].first) {
            mp[women[cur].second]++;
            cur++;
        }
        auto it = mp.lower_bound(men[i].second);
        if (it != mp.end()) {
            (*it).second--;
            ans++;
            if ((*it).second == 0) {
                mp.erase(it);
            }
        }
    }
    cout << ans << endl;
    return 0;
}