[ZJOI2008]泡泡堂BNB(贪心)

题意：传送门

题解：算浙江省最多赢多少分，用田忌赛马，算浙江省最少得多少分，另一方用田忌赛马，然后用2*n-ans即可，关于田忌赛马这个贪心还是挺多坑的，想了很多才算过了。

首先我们考虑的是我要赢更多，那么我尽量亏对方，如果我的最快的马比他的最快的马快，那么直接两个最快的马赛一场，肯定啊，我用最快的马不赢他最快的马，莫不成赢他的弱马去，然后如果我的最快的马比他的最快的马慢，那么我就肯定会输一把，不如要输这一把，那我就耍个心眼，用个最烂的马去和他赛，然后我赢的或平的只会不变或者增长，这就把对方坑的不行了，还有一种情况就是我的最快的马和对方最快的相同，然后我看下两个弱马，如果两个我的弱马还比它的弱马还如弱，既然都要输，不如将我最弱的这匹马和他最快的马赛，如果我的弱马和他的弱马强，那么我就用弱马赢一场，如果此时还用弱马和对方的强马比，就有很大的几率失去最优解，这个点卡了我好久，太弱了，比如这个样例：

3
10 10 5
10 10 2
           

具体看代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+5;

int n;

int tianjisaima(int *z,int *d)
{
    int sum=0,l1=1,r1=n,l2=1,r2=n;
    while(l1<=r1&&l2<=r2){
        if(z[r1]>d[r2]){
            sum+=2;
            r1--;r2--;
        }else if(z[r1]<d[r2]){
            l1++;
            r2--;
        }else{
            if(z[l1]>d[l2]){
                sum+=2;
                l1++;l2++;
            }else{
                if(z[l1]<d[r2]){
                    l1++;
                    r2--;
                }else if(z[l1]==d[r2]){
                    sum+=1;
                    l1++;
                    r2--;
                }
            }
        }
    }
    return sum;
}

int main()
{
    int z[maxn],d[maxn];
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&z[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&d[i]);
    }
    sort(z+1,z+n+1);
    sort(d+1,d+n+1);
    int ans1=tianjisaima(z,d);
    int ans2=tianjisaima(d,z);
    ans2=2*n-ans2;
    printf("%d %d\n",ans1,ans2);
    return 0;
}