田忌赛马问题,首先我们用田忌最慢的马去和皇帝最慢的马比,如果可以赢就,赢,不可以赢就去和他最大的马比,输,如果相等,用田忌最快的马和皇帝最快的马比,如果赢就,赢,不赢就用最慢的马比,输。这样就能效益最大化。
题目:http://acm.hdu.edu.cn/showproblem.php?pid=1052
代码:
Memory: 1748 KB | Time: 31 MS | |
Language: C++ | Result: Accepted |
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int maxn=1000+10; int n, i, j, tian[maxn], king[maxn], ans, tmin, tmax, kmin, kmax; bool cmax(int a, int b) { return a>b; } int main() { while(~scanf("%d", &n) && n) { ans=0; tmax=kmax=0; tmin=kmin=n-1; for(i=0;i<n;i++)scanf("%d", &tian[i]); for(i=0;i<n;i++)scanf("%d", &king[i]); sort(tian, tian+n, cmax); sort(king, king+n, cmax); while(1) { if(tian[tmin]>king[kmin]) { ans+=200; //最慢的马比,赢 tmin--; kmin--; } else if(tian[tmin]<king[kmin]) { if(tian[tmin]<king[kmax])ans-=200; //最慢的马比,输 tmin--; kmax++; } else { if(tian[tmax]>king[kmax]) { ans+=200; //最快的马比,赢 tmax++; kmax++; } else if(tian[tmax]<=king[kmax]) { if(tian[tmin]<king[kmax])ans-=200; //最快的马比,输 tmin--; kmax++; } } if(tmax>tmin)break; } printf("%d\n", ans); } return 0; }