HDU 1052

Tian Ji -- The Horse Racing HDU 1052

顿时吓尿了：

结题思路：

1.若田忌最慢的马可以战胜齐王最慢的马，那么就让它战胜那匹慢马，胜利场次加1。（田忌最慢马 > 齐王最慢马）

2.若田忌最慢的马不能战胜齐王最慢的马，那么它更加不能战胜其他的马，那就让它输，而且输给齐王最快马，失败场次加1。（田忌最慢马 < 齐王最快马）

3.若田忌最慢的马与齐王最慢的马速度相等。此时，不能简单地认为与它打成平手就是最好情况，相反，打平是下下策，为什么呢？

因为自己后面的队友很有可能战胜此时对方的这匹慢马，所以就算自己输一场，队友也能帮忙赢回一场，而胜一场，输一场的收益和打平一场的收益是一样的，而且自己输的时候可以拉对方最快的马下水，给己方最快的马创造更大的胜利机会（因为它失去了一个强劲的对手），也就是说己方最快的马很可能因为自己的牺牲再胜利一场，从这个角度看，还是自己故意输掉比较好。

但是，还有一点需要注意，当自己放水前，如果己方最快的马原本就比对方最快的马快，然后还输给对方最快的马，那么己方最快的马的才华就浪费了，为什么？

很简单，它原本就能赢，需要你放水么？- -！换句话说，这种情况下，自己的牺牲没有一点价值。

所以，在放水时，一定要保证己方最快马不快于对方最快马。满足此条件后，让己方最慢马与对方最快马去比赛（有可能平局），这样，田忌的马就得到了充分的利用。

转载于：http://blog.csdn.net/dgq8211/article/details/7370765

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<string.h>
 4 #include<stdio.h>
 5 using namespace std;
 6 int a[1005],b[1005];
 7 int main()
 8 {
 9     int i,n,j,d,win,lose,t_low,t_fast,k_low,k_fast;
10     while(scanf("%d",&n)!=EOF)
11     {
12         if(n==0)
13             break;
14         for(i=1;i<=n;i++)
15             scanf("%d",&a[i]);
16         for(i=1;i<=n;i++)
17             scanf("%d",&b[i]);
18         sort(a+1,a+n+1);
19         sort(b+1,b+1+n);
20         win=0;lose=0;t_low=1;t_fast=n;k_low=1;k_fast=n;
21         while(t_low<=t_fast)
22         {
23             if(a[t_low]>b[k_low])
24             {
25                 win++;
26                 t_low++;
27                 k_low++;
28             }
29             else if(a[t_low]<b[k_low])
30             {
31                 lose++;
32                 t_low++;
33                 k_fast--;
34             }
35             else
36             {
37                 if(a[t_fast]>b[k_fast])
38                 {
39                     win++;
40                     t_fast--;
41                     k_fast--;
42                 }
43                 else
44                 {
45                     if(a[t_low]<b[k_fast])
46                             lose++;
47                     k_fast--;
48                     t_low++;
49                 }//这里多多注意
50             }
51         }
52         printf("%d
",200*(win-lose));
53 
54     }
55     return 0;
56 }