HDU-1052 Tian Ji -- The Horse Racing 题解

题目大意

田忌赛马。

解题思路

贪心。

（今天比赛的时候碰到了差不多的题，以前写的题目差不多忘了，现在来补一下题解。。

先对两个人的马匹进行从大到小的排序。

如果我的最好的马，打不过他最好的马，那我用我的最差的马去对他最好的马。

如果我的最好的马，与他的最好的马打成平手，那我就需要考虑最差的马。

如果我最差的马打得过他最好的马，那我直接与他最差的马对上即可。

如果打不过，那就用我最差的马去对上他最好的马。

如果我的最好的马能打得过他最好的马，那我直接获胜即可。

完整代码

#include<stdio.h>
#include<algorithm>
#include<functional>
using namespace std;

int main() {
    int a[2000]= {0},b[2000]= {0},n;
    while(~scanf("%d",&n)&&n) {
        int cnt=0;
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        for(int i=1; i<=n; i++)
            scanf("%d",&b[i]);
        sort(a+1,a+1+n,greater<int>());
        sort(b+1,b+1+n,greater<int>());
        int i=1,j=n,l,r=n;
        for(l=1; l<=r&&i<=j;) {
            if(a[i]>b[l]) {
                i++;
                l++;
                cnt+=200;
            } else if(a[i]==b[l]) {
                if(a[j]<=b[r]) {
                    if(a[j]<b[l])
                        cnt-=200;
                    j--;
                    l++;
                } else {
                    cnt+=200;
                    r--;
                    j--;
                }
            } else {
                j--;
                l++;
                cnt-=200;
            }
        }
        printf("%d\n",cnt);
    }
}