TYVJ 1048 田忌赛马 贪心解法

描述

    中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了，他们各派出N匹马，每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢取最多的钱？

输入格式

第一行为一个正整数n (n <= 1000) ，表示双方马的数量。
第二行有N个整数表示田忌的马的速度。
第三行的N个整数为齐王的马的速度。

输出格式

仅有一行，为田忌赛马可能赢得的最多的钱，结果有可能为负。

测试样例1

输入

3 
92 83 71 
95 87 74

输出

200

/*
    首先，双方的马按速度排序。
    考虑己方最弱的马和对方最弱的马的速度关系。如果对方更弱，那么不妨就用这匹马去对对方的那匹马；如果我方更弱，那么不妨用这匹马和对方当前最强的马比赛。（平局稍后再说）
    同样地，可以考虑己方最强的马和对方最强的马的关系。
    不停地贪心处理，直到双方最强的马相等、最弱的马也相等。
    再考虑己方最弱马 和对方最强马的关系  
    相等就强制让这两局平局发生。
    否则就耗掉对方最强马 
    继续处理，直到所有的马都用完。
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#define MAXN 10010

using namespace std;

int a[2][MAXN];

int n,ans;

inline void read(int &x) {
    int f=1;x=0;char c=getchar();
       while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-48;c=getchar();}
       x=x*f;
}

int main() {
    read(n); 
    for(int i=1;i>=0;i--) //a[1]代表田忌 a[0]代表齐王 
      for(int j=1;j<=n;j++)
        read(a[i][j]);
    sort(a[0]+1,a[0]+1+n);
    sort(a[1]+1,a[1]+1+n);
    int tl=1,tr=n,jl=1,jr=n;
    while(tl<=tr) {
        if(a[1][tl]>a[0][jl]) {tl++;jl++;ans++;continue;}
        else if(a[1][tl]<a[0][jl]) {tl++;jr--;ans--;continue;}
        else if(a[1][tl]==a[0][jl]) {
            if(a[0][jr]<a[1][tr]) {tr--;jr--;ans++;continue;}
            else if(a[1][tr]<a[0][jr]) {ans--;tl++;jr--;continue;}
            else if(a[1][tr]==a[0][jr]) {
                if(a[1][tl]==a[0][jr]) {tl++;jr--;continue;}
                else if(a[1][tl]<a[0][jr]) {tl++;jr--;ans--;continue;}
            }
        }
    }
    printf("%d
",ans*200);
    return 0;
}