题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=1052
唉,虽是贪心,还是未能理解透啊:
1,从田忌最差的马开始,能胜利就胜利,而且将胜利最大化
2,把剩下的不能取胜的最差的马依次与王剩下最的好的马匹配即可,其中可能还会有平局,记录即可
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int Tian[1500],King[1500],vist[1500],visk[1500];
int n;
int cmp(int a,int b){
return a>b;
}
int main(){
while(cin>>n)
{
if(!n) break;
for(int i=0;i<n;i++)
cin>>Tian[i];
for(int i=0;i<n;i++)
cin>>King[i];
sort(Tian,Tian+n,cmp);
sort(King,King+n,cmp);
memset(vist,0,sizeof(vist));
memset(visk,0,sizeof(visk));
int win=0,fair=0;
for(int i=n-1;i>=0;i--)
{
int ti=n;
for(int j=n-1;j>=0;j--)
if(Tian[i]>King[j] && !visk[j])
ti=j;
if(ti!=n) {
win++;
visk[ti]=1;
vist[i]=1;
}
}
for(int i=n-1;i>=0;i--)
if(!vist[i]){
for(int j=0;j<n;j++){
if(!visk[j])
{
if(Tian[i]==King[j]) fair++;
vist[i]=1;
visk[j]=1;
break;
}
}
}
cout<<(2*win-n+fair)*200<<endl;
}
return 0;
}