hdu 1052 Tian Ji -- The Horse Racing
http://acm.hdu.edu.cn/showproblem.php?pid=1052
自认为没问题的程序提交上去竟然给我WA，我的心真是“呱凉呱凉”的啊。当它AC的那一刻，百感交集……
嘿嘿，题目其实很简单，但你必须得理清思路才行。
思路：(对我的代码的解说)
1： 把田忌马和齐王马分别按速度由大到小排序
2： 找出齐王马中 按顺序第一头 速度小于或等于田忌马的那头马的编号 i (在这里编号从0开始)
3: 这个 i 就相当于前面田忌比输的比赛场数，故首先初始化，田忌赢得的钱 sum = - i * 200 ;
……（省略，关键讲他们是怎么比的，请结合我的代码看这个。因为表达有限 ）
4： 田忌马的头号马T[ T_start ] 与齐王马的头号马 K[ K_start ] (开始的时候 K_start = i)比较
→→4.1 如果 T[ T_start ] > K[ K_start ] ，则田忌比赢一场， sum += 200, T_start ++,K_start++
→→4.2 如果 T[ T_start ] < K[ K_start ] ，则田忌比输一场， sum -= 200, T_start ++,K_start++
→→4.3 如果T[ T_start ] == K[ K_start ]（最麻烦，也是最容易出错的）
→→→→4.3.1如果T[ T_end ] > K[ K_end ] ,则用最后一头田忌马与最后一头齐王马比赛，田忌赢一场
→→→→→→→sum+=200,T_end--,K_end--;
→→→→4.3.2如果T[T_end] < K[K_end] ,则用最后一头田忌马与最前一头齐王马比赛，田忌输一场
→→→→→→→sum-=200,T_end--,K_start++;
→→→→4.3.3如果T[T_end]==K[K_end],则用田忌马最后一头与齐王马最前一头比【还要转个弯】
→→→→→→→4.3.3.1如果T[T_end]<K[K_start],田忌输一局,sum-=200,T_end--,K_start++;
→→→→→→→4.3.3.2如果T[T_end]==K[K_start],比赛平局,sum不变,T_end--,K_start++;
5：判断是否 K_start > K_end ,如果不是，则返回 4，否则 跳出循环
6：输出
代码如下：
#include<iostream>#include<cstdio>#include<algorithm>using namespace std;int T[1001],K[1001];int cmp(const int &a,const int &b){ return a>b?1:0;}int main(){ int n; while(scanf("%d",&n)>0&&n) { int i; for(i=0;i<n;i++) cin>>T[i]; for(i=0;i<n;i++) cin>>K[i]; sort(T,T+n,cmp); sort(K,K+n,cmp); i=0; while(i<n) { if(T[0]>=K[i]) break; i++; } int sum = -i*200; int T_end=n-1-i,T_start=0,K_end=n-1,K_start=i; while(K_start<=K_end) { if(T[T_start] < K[K_start]) { sum -= 200; T_end--; K_start++; }else if(T[T_start]>K[K_start]) {sum += 200;T_start++; K_start++; }else{if(T[T_end]>K[K_end]){sum+=200;T_end--;K_end--;}else if(T[T_end]<K[K_end]){sum-=200;T_end--;K_start++;}else{if(T[T_end] < K[K_start])sum -= 200;T_end--;K_start++;}} } printf("%d\n",sum); }return 0;}