田忌赛马-题解

· · 题解

查看原题请戳这里
非常经典的一道贪心。
我们先对田忌的马和齐王的马进行排序，由于哪两匹马进行比赛完全由田忌决定，所以这一步不会导致错误。
然后我们来考虑以下几种情况：

  1. 当田忌最慢的马比齐王最慢的马快，赢一场。因为始终要赢齐王最慢的马，不如用最没用的马来赢它。
  2. 当田忌最慢的马比齐王最慢的马慢，和齐王最快的马比，输一场。因为田忌最慢的马始终要输的，不如用它来消耗齐王最有用的马。
  3. 当田忌最慢的和齐王最慢的马慢相等时，分4，5，6讨论。
  4. 当田忌最快的马比齐王最快的马快时，赢一场先。因为最快的马的用途就是来赢别人快的马，别人慢的马什么马都能赢。
  5. 当田忌最快的马比齐王最快的马慢时，拿最慢的马和齐王最快的马比，输一场，因为反正要输一场，不如拿最没用的马输。
  6. 当田忌最快的马和齐王最快的马相等时，这就要展开讨论了，贪心方法是，拿最慢的马来和齐王最快的马比。

这就是我们的贪心策略了。
证明：

对于第6种贪心策略的证明如下：采用调整的思想。
设 齐王最快的马为a1,最慢的马为an；
田忌最快的马为b1,最慢的马为bn。
此处不考虑全部相等(a1=a2=a3=…=an,b1=b2=b3=…=bn)
因为这种情况显然成立
所以当a1=b1,an=bn时， ai为齐王比赛中的某一匹马。
1.当an=ai时，
用bn与ai比赛，因为an=bn，所以ai=an=bn，所以这场比赛结果是平局。再用a1与b1比赛，结果平局，总得分为0分。
如果用b1去与ai比赛，结果为胜利。再用bn去与a1比较，结果为失败，总得分为0分，结果不变。
2.当an<ai时，
用bn与ai比赛，因为an=bn，所以ai>an=bn，所以这场比赛结果是失败。再用a1与b1比赛，结果平局，总得分为-200分。
如果用b1与ai比赛，结果为平局或胜利。再用bn去与a1比较，结果为失败，总得分为0分或-200分，结果比原方法更优。
附一下代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

int n,t[2005],q[2005],ans;

int mysort(int a,int b){return a > b;}

int main()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%d",&t[i]);
    for(int i = 1; i <= n; i++) scanf("%d",&q[i]);
    sort(t + 1, t + n + 1, mysort);
    sort(q + 1, q + n + 1, mysort);
    int p1 = 1, p2 = 1,p3 = n,p4 = n;
    while(p1 <= n && p2 <= n && p1 <= p3 && p2 <= p4)
    {
        if(t[p1] > q[p2])
        {
            ans += 200;
            p1 ++;
            p2 ++;
        }
        if(t[p1] < q[p2])
        {
            ans -= 200;
            p2 ++;
            p3 --;
        }
        if(t[p1] == q[p2])
        {
            if(t[p3] > q[p4]) 
            {
                ans += 200;
                p3 --; p4 --;
            }
            else 
            {
                if(t[p3] < q[p2]) ans -= 200;
                p3 --;
                p2 ++;
            }

        }
    }
    printf("%d\n",ans);
    return 0;
}