HDU 1052(田忌赛马 贪心)

题意是田忌赛马的背景，双方各有n匹马，下面两行分别是田忌和齐王每匹马的速度，要求输出田忌最大的净胜场数*每场的赌金200。

开始的时候想对双方的马匹速度排序，然后比较最快的马，能胜则胜，否则用最慢的马去消耗对方，但这样存在问题：1 2 3 对 1 3 3的时候，会变成1 - 3,2 - 3,3 - 1，净胜-1场，而实际存在1 - 3,2 - 1,3 - 3的净胜0场的策略；

然后自然想到的是要对平局进行特殊处理，当双方最快的马能战平时，比较最慢马，如果最慢马能胜对方，就用最慢马胜对方，然后让两方最快马战平，但是：2 3 5 对 1 4 5的时候，会变成 2 - 1,3 - 4,5 - 5，净胜0场，而实际存在2 - 1,3 - 5,5 - 4的净胜1场的策略；

......

惊觉自己不断拆墙补墙的做法导致自己的策略不够完整，逻辑也不够严密，借鉴了别人的代码，才得出较为严密的策略：

以双方最慢的马比较，若田忌最慢的马比齐王最慢的马快，则本场用双方最慢的马比赛；若田忌最慢的马比齐王最慢的马慢，则本场用田忌最慢的马和齐王最快的马比赛；若两方最慢的马速度一样，则比较两方最快的马；若田忌最快的马快于齐王最快的马，本场用双方最快的马比赛，（若田忌最快的马和齐王最快的马一样快，暂不处理，保留；若田忌最快的马比齐王最快的马慢，则用田忌最慢的马去消耗齐王最快的马。）这里只比较田忌最慢的马和齐王最快的马即可。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 int main()
 5 {
 6     int cnt,n,pafast,pbfast,paslow,pbslow,ans,a[1009],b[1009];
 7     while(~scanf("%d",&n)&&n)
 8     {
 9         for(int i = 0; i < n; i++)  scanf("%d",&a[i]);
10         for(int i = 0; i < n; i++)  scanf("%d",&b[i]);
11         sort(a,a+n);
12         sort(b,b+n);
13         pafast = pbfast = n-1;
14         paslow = pbslow = 0;
15         ans = cnt = 0;
16         for(int i = 0; i < n; i++)
17         {
18             if(a[paslow] > b[pbslow])  //当前田忌慢马快于齐王慢马
19             {
20                 paslow++;
21                 pbslow++;
22                 ans++;
23             }
24             else if(a[paslow] < b[pbslow])  //当前田忌慢马慢于齐王慢马，选择与齐王快马比
25             {
26                 paslow++;
27                 pbfast--;
28                 ans--;
29             }
30             else   //当前田忌慢马与齐王慢马一样
31             {
32                 if(a[pafast] > b[pbfast])   // 当前田忌快马快于齐王快马
33                 {
34                     pafast--;
35                     pbfast--;
36                     ans++;
37                 }
38                 else if(a[paslow] < b[pbfast])    // 当前田忌慢马慢于齐王快马，选择与齐王快马比
39                 {
40                     paslow++;
41                     pbfast--;
42                     ans--;
43                 }
44             }
45         }
46         printf("%d\n",ans*200);
47     }
48     return 0;
49 }

View Code

个人觉得非常漂亮的分析：

（希望以后也能写出如此漂亮的分析...）