LA3266田忌赛马

题意：

田忌和齐王赛马，两个人每人n匹马，每个马都有自己的速度，赢一场得到200分，输一场失去200分，平则不得分，问田忌可能得到的最高得分是多少？

思路:

又是一个比较经典的贪心小题目，这个题目很容易想到，就是我们先排序，然后我们这样想，如果我们是田忌，对方是齐王，首先我们可以拿最快的那个马和他最快的那个马比一下，如果能赢，那么直接比赛，得到一分，这个不用质疑，因为用自己的最强去得分的同时还削弱的对方的最强，这个果断是最优的，然后如果比不过呢？比不过就有可能面临着这一局要输的节奏，反正也是输，我们就找一个我们最小的去和他最大的比，去浪费他的最大的，这样输的有价值，但是这是后要注意一点，就是如果我们最小的比他的最小的大，那么我们还不如用我们最小的和他的最小的比一次，先赢200分，前面的那个打不过先放一下，在处理晚处理都一样，现在能赢一次是一次，那么整理后就是这样：先用最想的和他最强的比，如果能打赢就打，否则就看看我们最弱的能不能打得过他的最弱的，如果能赢就直接比，否则就拿最弱的去换他最强的，输的有价值点，还有就是有一个小地方要注意，如果我们打算用最弱的换最强的了，发现最弱的和他最强的一样，那么这时候我们是不输钱的，其实这个时候应该是直接可以break了吧，我没想错的话这个时候双方剩下的所有马的速度都是一样的。

#include<stdio.h>

#include<algorithm>

#define N 1000 + 10

using namespace std;

bool camp(int a ,int b)

{

return a > b;

}

int num1[N] ,num2[N];

int main ()

{

int i ,n ,l1 ,l2 ,r1 ,r2, Ans;

while(~scanf("%d" ,&n) && n)

{

for(i = 1 ;i <= n ;i ++)

scanf("%d" ,&num1[i]);

for(i = 1 ;i <= n ;i ++)

scanf("%d" ,&num2[i]);

sort(num1 + 1 ,num1 + n + 1 ,camp);

sort(num2 + 1 ,num2 + n + 1 ,camp);

l1 = l2 = 1 ,r1 = r2 = n;

Ans = 0;

while(n--)

{

if(num1[l1] > num2[l2])

{

l1 ++ ,l2 ++;

Ans ++;

}

else if(num1[r1] > num2[r2])

{

r1 -- ,r2 --;

Ans ++;

}

else

{



if(num1[r1] < num2[l2])

Ans --;

r1 -- ,l2 ++;



}

}

printf("%d\n" ,Ans * 200);

}

return 0;

}

巴特西

LA3266田忌赛马

最新文章

热门文章