POJ 2287 Tian Ji -- The Horse Racing(贪心)

POJ 2287 Tian Ji -- The Horse Racing(贪心)

http://poj.org/problem?id=2287

题意:

(前面一大段背景介绍…)其实就是田忌和国王各有n匹马且给出了每匹马的速度.现在进行n轮比赛,如果田忌胜1局得200银币,输一局扣200银币.问田忌最多获得多少银币.(可能为负数)

分析:

首先比赛肯定是要比n局的,所以想要获得最大的钱数,我们必须让胜的局数越多越好.

首先我想到的贪心策略是,将田忌和齐王的马都按速度从小到大排序,对于齐王的每匹马,我们都劲量用田忌所有马中速度最小但是能胜齐王的马来比赛.这样我们能保证胜的场数最多.

上面的策略和结论是对的,但是有个问题没考虑到.比赛有3种结果(而不仅仅是胜和负),胜,负,平局. 上面的策略可以保证我们的胜局数是最多的,但是不能保证负局数最少(因为还有平局在其中).

比如下面例子:

1 2 2 2 2 5

1 2 3 3 3 7

正常一眼可以看出上面的最优解是:胜2局,平1局,负3局.但是如果按上面的思路那就是胜2局,负4局. 所以上面的思路是不正确的.

下面是网上的思路,对于当前集合的所有马: (用A代表田忌,B代表齐王)

1.如果A最快的马比B最快的马快,那么肯定用A最快马和B最快马比.(因为如果拿A的其他马来和B最快马比赛的话,如果输了可能更差,会使得负局更多,胜局更少. 但如果赢了也不会更好.)

2.如果A最快的马比B最快的马慢,那么直接用A最慢的马和B最快的马比.(因为A中没有马比B最快的马快,还不如让A中最慢的马去输)

3.如果A最快马速度 == B最快马速度,那么比较A最慢的马和B最慢的马速度:

3.1 A最慢马速度胜过B最慢的马速度,那就用A最慢的马与B最慢的马比.(A中所有马肯定都胜过B最慢的马了,B最慢的马肯定要比一局的,就不浪费资源了)

3.2 A最慢马速度 <=B最慢马的速度,那么就用A最慢的马与B最快的马比.(既然A最慢的马谁也胜不了,不如让A去输给B最快的马.说不定A中别的马能胜B中最慢的马呢…)

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1000+10;
int v1[maxn],v2[maxn];
int main()
{
    int n;
    while(scanf("%d",&n)==1&&n)
    {
        for(int i=0;i<n;i++)
            scanf("%d",&v1[i]);
        for(int i=0;i<n;i++)
            scanf("%d",&v2[i]);
        sort(v1,v1+n);
        sort(v2,v2+n);

        int ans=0;//最后得分
        int cnt=n;//要比n局
        int max1=n-1,max2=n-1;//指向田忌和齐王当前马集合中速度最快的马
        int min1=0,min2=0;    //指向田忌和齐王当前马集合中速度最慢的马
        while(cnt--)
        {
            if(v1[max1] > v2[max2])
            {
                ans +=200;
                max1--,max2--;
            }
            else if(v1[max1] < v2[max2])
            {
                ans -=200;
                min1++,max2--;
            }
            else
            {
                if(v1[min1] > v2[min2])
                {
                    ans +=200;
                    min1++,min2++;
                }
                else
                {
                    if(v1[min1] <v2[max2]) ans -=200;
                    min1++,max2--;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}