TechFUL: Fair or UnFair

TechFUL TechFUL: 中級 貪欲法

問題概要

Tech ちゃんと FUL ちゃんは 2 \times N 枚のカードを用いて遊ぶことにした．

i 枚目のカードには数字 a_{i} が書かれている．

Tech ちゃんと FUL ちゃんは交互にデッキから好きなカードを 1 枚ずつ取り出す．

デッキがなくなったとき、Tech ちゃんと FUL ちゃんはカードを N 枚ずつ持っている．

Tech ちゃんと FUL ちゃんは N 回のラウンドでカードの数字の大きさ比べを行う．

より大きい数字を出した方が勝ちであり、同じ数字であれば引き分けとなる．

毎回のラウンドで Tech ちゃんが先にカードを出すとき、FUL ちゃんの勝利回数の最大値を求めよ．

但し、Tech ちゃんと FUL ちゃんが自分の勝ちを最大化できるよう最善を尽くすものとする．

制約

  • 1 \le N \le 10^{5}

  • 1 \le a_{i} \le 10^{5}

考えたこと

数字が大きいカードが有利なので、Tech ちゃんと FUL ちゃんがデッキから選ぶカードは一意に決まる．

具体的には、 2 \times N 枚のカードを大きい順に交互に選択する．

Tech ちゃんが選んだカードを大きい順に T_{1}, T_{2}, \ldots, T_{N} とする．

また、FUL ちゃんが選んだカードを大きい順に F_{1}, F_{2}, \ldots, F_{N} とする．

i_{1} を T_{i_{1}} \lt F_{1} を満たす 1 以上 N 以下の最小のインデックスとする．

Tech ちゃんがカード T_{i_{1}} を出すとき、FUL ちゃんは F_{1} を出すのが最適である．

続いて、 i_{2} は T_{i_{2}} \lt F_{2} を満たす i_{1} + 1 以上 N 以下の最小のインデックスとする．

Tech ちゃんがカード T_{i_{2}} を出すとき、FUL ちゃんは F_{2} を出すのが最適である．

同様にして、FUL ちゃんが F_{3}, F_{4}, \ldots を出すのが最適であるような Tech ちゃんのカードを求めることができる．

下図を例にすると、

  • i_{1} = 2 より、Tech ちゃんが T_{2} = 5 を出すとき、FUL ちゃんは F_{1} = 6 を出すべきである．

  • i_{2} = 3 より、Tech ちゃんが T_{3} = 4 を出すとき、FUL ちゃんは F_{2} = 5 を出すべきである．

  • i_{3} = 5 より、Tech ちゃんが T_{5} = 1 を出すとき、FUL ちゃんは F_{3} = 4 を出すべきである．

  • i_{4} = 6 より、Tech ちゃんが T_{6} = 1 を出すとき、FUL ちゃんは F_{4} = 2 を出すべきである．

  • Tech ちゃんが T_{1} = 7, T_{4} = 4 を出すとき、FUL ちゃんは F_{5} = 1, F_{6} = 1 から適当に出せばいい．

f:id:legosuke_prog:20200528094157p:plain

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

int main() {
    int N;
    cin >> N;
    vector<int> a(2 * N);
    for (int i = 0; i < a.size(); ++i) {
        cin >> a[i];
    }
    sort(a.begin(), a.end(), greater<int>());
    vector<int> T, F;
    for (int i = 0; i < N; ++i) {
        T.push_back(a[2 * i]);
        F.push_back(a[2 * i + 1]);
    }
    int ans = 0, i = 0, j = 0;
    while (i < N && j < N) {
        if (T[i] < F[j]) {
            j++;
            ans++;
        }
        i++;
    }
    cout << ans << endl;
}