[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;
}