田忌赛马

田忌赛马-题解

Azuree

·

2019-07-16 11:14:56

·

题解

查看原题请戳这里

非常经典的一道贪心。

我们先对田忌的马和齐王的马进行排序，由于哪两匹马进行比赛完全由田忌决定，所以这一步不会导致错误。

然后我们来考虑以下几种情况：

当田忌最慢的马比齐王最慢的马快，赢一场。因为始终要赢齐王最慢的马，不如用最没用的马来赢它。

当田忌最慢的马比齐王最慢的马慢，和齐王最快的马比，输一场。因为田忌最慢的马始终要输的，不如用它来消耗齐王最有用的马。

当田忌最慢的和齐王最慢的马慢相等时，分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

用bn与ai比赛，因为an=bn，所以ai>an=bn，所以这场比赛结果是失败。再用a1与b1比赛，结果平局，总得分为-200分。

如果用b1与ai比赛，结果为平局或胜利。再用bn去与a1比较，结果为失败，总得分为0分或-200分，结果比原方法更优。

附一下代码：

#include

#include

#include

#include

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;

}