田忌赛马，完全没看出是贪心算法，我大概是忘记贪心算法是什么了，以至于看了思路解析也没看出是贪心算法 = = 考虑的时候只考虑到了 (1)若田忌最慢的马比齐王最慢的马慢，则将田忌最慢的马VS齐王最快的马 (2)若田忌最慢的马比齐王最慢的马快，则比较。 完全没考虑到最快的马的情况和马的速度相等时的分情况讨论。代码也没写出来。 看了网上的解题思路，完善如下 （1）若田忌最慢的马比齐王最慢的马快，则比较。赢 （2）若田忌最慢的马比齐王最慢的马慢，则将田忌最慢的马VS齐王最快的马，输 （3）若田忌最慢的马与齐王最慢的马速度相当，考虑以下情况 3.1若田忌最快的马比齐王最快的马快，则将田忌最快的马VS齐王最快的马，赢 3.2若田忌最快的马比齐王最快的马慢，则将田忌最慢的马VS齐王最快的马，输 3.3若田忌最快的马与齐王最快的马速度相当，则将田忌最慢的马VS齐王最快的马，（分为两平或一输一赢，结果都是平）平
#include <iostream> #include <stdio.h> #include <math.h> #include <algorithm> #include <string.h> using namespace std; const int MAXN=1010; int a[MAXN],b[MAXN]; int main () { int m,j,k,p,q,sum; while(scanf("%d",&m)==1&&m) { int i; for( i=0; i<m; i++) { scanf("%d",&a[i]); } for(i=0; i<m; i++) { scanf("%d",&b[i]); } sort(a,a+m); sort(b,b+m); j=k=m-1; p=q=sum=0; while(p<=j&&q<=k) { if(a[p]>b[q]) { sum+=200; p++; q++; //continue; } else if(a[p]<b[q]) { sum-=200; p++; k--; //continue; } else { if(a[j]>b[k]) { sum+=200; j--; k--; //continue; } else if(a[j]<b[k]) { sum-=200; p++; k--; //continue; } else { if(a[p]<a[k]) { sum-=200; p++; k--; //continue; } else if(a[p]==b[k]) { break; } } } } printf("%d\n",sum); } return 0; }不知道为什么超时，已经崩溃= =
