P1797 求解田忌赛马问题

问题描述

两千多年前的战国时期，齐威王与大将田忌赛马。双方约定每人各出 300 匹马，并且在上、中、下 3 个等级中各选一匹进行比赛，由于齐威王每个等级的马都比田忌的马略强，比赛的结果可想而知。现在双方各 n 匹马，依次派出一匹马进行比赛，每一轮获胜的一方将从输的一方得到 200 银币，平局则不用出钱，田忌已知所有马的速度值并可以安排出场顺序，问他如何安排比赛获得的银币最多？

Tip: 本题为单组输入

输入描述

第 1 行，一个正整数 n (n le 100000)n(n≤100000)，表示马的数量； 后两行分别是 nn 个整数，表示田忌和齐威王的马的速度值。

输出描述

每个测试用例输出一行，表示田忌获得的最多银币数。

样例输入

Copy to Clipboard

3 92 83 71 95 87 74 

样例输出

Copy to Clipboard

200

#include 
#define LL long long 
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e9 + 10;
const int N = 2e+7;
int a[N];
int b[N];
int n;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
    }
    for(int i = 1;i <= n;i ++){
        cin >> b[i];
    }
    sort(a + 1,a + n + 1,greater());
    sort(b + 1,b + n + 1,greater());
    // for(int i = 1;i <= n;i ++ )
    //     cout << a[i] << endl;

    int ans=0;
    for(int i=1,j=1,ii=n,jj=n;i<=ii;){
        if(a[i] > b[j]){
            i++;
            j++;
            ans += 200;
        }
        else if(a[i] < b[j]){
            ii--;
            j++;
            ans -= 200;
        }
        else{
            if(a[ii] > b[jj]){
                ii--;
                jj--;
                ans+=200;
            }
            else{
                if(a[ii] < b[j])
                    ans -= 200;
                j++;
                ii--;
            }
        }
    }

    cout << ans << endl;

    return 0;
}