1. 田忌赛马
典型的贪心算法~~自己木有考虑到贪心的第二步导致wa了好多次
算法分析
Problem Description：
给出2N组数据，分别表示田忌和齐威王的N匹马的速度，没进行一场比赛（每组数据共N场场赛），若能分出胜负，则输的一方要给赢的一方200Y￥（银元），求田忌以怎样的策略才能赚取最多的老婆本。
Solution：这题有多种解体思路，DP，二分图最大匹配算法等，这里给出的是比较容易理解的贪心算法，具体思路如下：
先将田忌跟齐王的马的速度数组进行一次冒泡排序
1、如果田忌最快的马比齐王最快的马快，则比之
2、如果田忌最快的马比齐王最快的马慢，则用田最慢的马跟齐最快的马比 //这是贪心的第一步
3、如果田忌最快的马的速度与齐威王最快的马速度相等
3.1、如果田忌最慢的比齐威王最慢的快，则比之 //这是贪心的第二步
3.2、如果田忌最慢的比齐威王最慢的慢，田忌慢VS齐王快
3.3、田忌最慢的与齐威王最慢的相等，田忌慢VS齐王快
注意这两种 数据
3
1 2 3
92 83 71 tian 第一步 tian1对king1 转到2 贪心的第一次，
95 92 74 king 第二步tian1对king2 转到3.1 （贪心的第二次 保留tian的快马 ）
第三步 只剩下一种选择了~~3 92 83 70 92 91 60
*********代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int a[3000],b[3000];
int cmp(int a,int b)
{
return a>b;
}
int main()
{
int i,n,j,sum,k,f,ji;
while( scanf("%d",&n) && n!=0 )
{
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
scanf("%d",&b[i]);
sort(a,a+n,cmp);
sort(b,b+n,cmp);
ji=0; // 记录 king 比赛用的马 循环跳出的判定条件
i=j=sum=0;
k=n-1;
f=n-1;
while(1)
{
if(ji==n) break; // king 的马全部比完后跳出
if(b[j]>a[i]) { sum-=200;j++;k--;ji++; continue;} //如果king的比tian的快马快 用tian的慢马对king的快马
if(b[j]==a[i]){ //如果相等
if(b[f]<a[k]){f--;k--;sum+=200;ji++;continue;} //看两人的慢马 tian的慢马比king的慢马快则比
if(b[j]>a[k]){sum-=200;k--;j++;ji++;}
else {k--;j++;ji++;}
continue;
}
if(b[j]<a[i]){sum+=200;j++;i++;ji++;continue;} //如果tian的比king的快马快 直接比
}
printf("%d\n",sum);
}
}
