本文共 849 字，大约阅读时间需要 2 分钟。

【题目】

Description

田忌和齐王赛马,两人各出n匹马,赢一场比赛得200两银子,输了赔200银子,平局不赔不赚.已知两人每匹马的速度,问田忌最多能赢多少银子.

Input

多组测试数据,

每组数据的第一行是一个整数n。 (1<=n<=1000)

第二行包括n个整数既田忌每匹马的速度.

第三行包括n个整数既齐王每匹马的速度.

每匹马的速度不超过1000.

Output

对于每组数据输出一行有一个整数代表田忌最多能赢多少银子

Sample Input

3 92 83 71  95 87 74 2 20 20 20 20 2 20 19 22 18

Sample Output

20000

【题意】

分别给定田忌的马和齐王的马的速度，要求输出使用最优策略田忌最多能赢多少银子。

【思路】

田弱跟齐弱比较，若田弱>齐弱，则田忌胜；田强跟齐强比较，若田强>齐强，则田忌胜；否则就拿田弱拉齐强下水，田忌输一场（当然如果是平局就不胜也不败）。

为什么要优先判断田强和齐强而不直接田弱拉齐强下水呢~因为，假如田弱=齐弱，而田强>齐强，如果田弱拉齐强下水，那么不就白白败一场了吗~

【代码】

#include 
   
    using namespace std;int main(){   int n,a[1005],b[1005];   while(~scanf("%d",&n))   {       for(int i=0;i
    
     b[jj]) ans++,ii--,jj--;           else if(a[i]>b[j]) ans++,i++,j++;           else           {               if(a[i]!=b[jj]) ans--;               i++,jj--;           }       }       printf("%d\n",ans*200);   }   return 0;}
    
   

转载地址：http://pyben.baihongyu.com/