首页 > 代码库 > hdu 1052 Tian Ji -- The Horse Racing
hdu 1052 Tian Ji -- The Horse Racing
Tian Ji -- The Horse Racing
题意：田忌赛马的问题，按照马的速度比较胜负，每胜一场得200分；求田忌比赛的最大值。
input 3 92 83 71 95 92 74 3 92 83 70 92 91 60 output 0 200 |
策略：1、田忌最快的马比王最快的马快，则直接比，赢一场。
2、田忌最快的马比王最快的马慢，则用田忌最慢的马和王最快的马比，输一场。
3、田忌最快的马和王最快的马速度一样：
用田忌最慢的马比王最慢的马快，则田忌最慢的马和王最慢的马比，赢一场；
否则，田忌最慢的马和王最快的马比，若王的马快，则输一场，否则，平一场、
#include"stdio.h"
#include"string.h"
#include"algorithm"
using namespace std;
#define N 1005
int cmp(int a,int b)
{
return a>b;
}
int main()
{
int i,n;
int a[N],b[N];
while(scanf("%d",&n),n)
{
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);
int c1,c2,a1,a2,b1,b2;
a1=b1=c1=c2=0;
a2=b2=n-1;
while(a1<=a2)
{
if(a[a1]>b[b1]) //田最快的马比王最快的马快
{
c1++;a1++;b1++;
}
else
{
if(a[a1]<b[b1]) //田最快的马比王最快的马慢
{
c2++;a2--;b1++;
}
else //田最快的马和王最快的马速度一样
{
if(a[a2]>b[b2]) //田最慢的马比王最慢的马快
{
c1++;a2--;b2--;
}
else
{
if(a[a2]<b[b1])
{
c2++;
}
a2--;b1++;
}
}
}
}
printf("%d\n",(c1-c2)*200);
}
return 0;
}
input 3 92 83 71 95 92 74 3 92 83 70 92 91 60 output 0 200 |
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。