首页 > 代码库 > HDU 1052

HDU 1052

2024-07-30 00:43:58   225人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=1052

田忌赛马本质就是一个贪心

res表示田忌的胜利场次

1、田忌最快马快于王的最快马，两个最快马比，res++

2、田忌最快马慢于王的最快马，田忌的最慢马和王的最快马比，res--

3、田忌最快马等于王的最快马，分三种情况

　  田忌最慢马快于王的最慢马，两个最慢马比，res++

　  田忌最慢马慢于王的最慢马，田忌的最慢马和王的最快马比，res--

     田忌最慢马等于王的最慢马，田忌的最慢马和王的最快马比，如果田忌的最慢马慢于王的快马res--（这个判断为了排除两个相等的情况，第二个样例给的非常厚道）

这题当年似乎让很多人饮恨，其实现场赛对于大多数队伍来讲，不用出什么真正的难题，需要的只是把这种题目做稳，理清思路，不慌张。当时会去敲二分图最大匹配的选手肯定已经乱了（因为理性思考的话，1000点的稠密图二分图最大匹配没有一丝生机，尽管1000看似诱人），同时不得不说，数据上限是1000的贪心非常阴险，如果出成10w应该会有更多人ac。

#include <iostream>#include <cstdio>#include <algorithm>using namespace std;int a[1005],b[1005];int main(){    int n,f1,r1,f2,r2;    while(~scanf("%d",&n),n){        for(int i=0;i<n;i++)            scanf("%d",&a[i]);        for(int i=0;i<n;i++)            scanf("%d",&b[i]);        sort(a,a+n);sort(b,b+n);        f1=f2=0;r1=r2=n-1;        int cnt=0;        int res=0;        while(1){            if(a[r1]>b[r2]){                res++;                r1--;r2--;            }            else if(a[r1]<b[r2]){                res--;                f1++;r2--;            }            else{                if(a[f1]>b[f2]){                    res++;                    f1++;f2++;                }                else if(a[f1]<b[f2]){                    res--;                    f1++;r2--;                }                else{                    if(a[f1]<b[r2])res--;                    f1++;r2--;                }            }            cnt++;            if(cnt==n)break;        }        printf("%d\n",res*200);    }    return 0;}
View Code

 

HDU 1052


联系
我们