题目
LA 3266 Tian Ji – The Horse Racing
题解
这神奇的贪心我是并没有想出来，只会做没有平局的情况，感觉自己太傻比，不知道怎么冲省选了。找的是这篇题解：http://blog.csdn.net/yeyeyeguoguo/article/details/43855417
以下思路为题解内容，感觉其实思路不大容易想到_ (:зゝ∠) _
题意:
田忌要和国王赛马,双方各有n只马,赢一场得200,输一场,失200,平局不给钱;问怎么安排田忌赚最多;思路:
首先第一步肯定是把双方的马都排序,然后先把最慢的马比一下,如果这马比国王快,直接赢下来,如果比国王慢那就用这匹马输给国王最快的马(反正都要输,尽量消耗他);
但是如果一样快,就要比较最快的那匹马,如果最快的那匹马比较快,也是直接赢下来,然后比较接下去最快的,如果最快的马小于或等于国王的,那就用慢的那匹去输(因为如果直接快对快,慢对慢,那么就是一平一负,用慢对快,就是那一负,但是快的那匹肯定会多赢一场下来,收获是一样的,但是这样做我们留下的一匹快的,对方留下一只慢的,后面可以做更好的安排)(如果快马也等于快马也是一样,把两平,换成一胜一负)
代码
//QWsin
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000+10;int n;
int a[maxn],b[maxn];inline int cmp(int a,int b){
return a>b;}inline void solve()
{for(int i=1;i<=n;++i) scanf("%d",a+i);for(int i=1;i<=n;++i) scanf("%d",b+i);sort(a+1,a+n+1);sort(b+1,b+n+1);int la=1,ra=n,lb=1,rb=n,cnt=0;while(la<=ra){if(a[la] > b[lb]) ++cnt,++la,++lb;else{if(a[ra] > b[rb]) ++cnt,--rb,--ra;else if(a[la++] < b[rb--]) --cnt;}}printf("%d\n",200*cnt);
}int main()
{while(scanf("%d",&n)==1&&n) solve();return 0;
}