还是杭电1052田忌赛马
//昨天那个算法漏洞挺大,但我重新构思了,但运行到312ms还是wa了。我测试了许多数据,结果是对的,郁闷了,谁能救救我啊?#include"stdio.h"
void sort(int s[],int n,int d[]) //选择排序
{
int i,j,t,k,e;
for(i=0;i<n-1;i++)
{
k=i;
for(j=i+1;j<n;j++)
if(s[k]<s[j])
k=j;
if(k!=i)
{
t=s[i];
s[i]=s[k];
s[k]=t;
e=d[i];
d[i]=d[k];
d[k]=e;
}
}
}
int main()
{
void sort(int s[],int n,int d[]);
int i,j,k,n,e,m;
int a[1001]={0},b[1001]={0},c[1001]={3}; //a用来存田忌马的数据,b存齐王的,c用来记录胜负平。
long sum;
while(scanf("%d",&n)!=EOF&&n!=0)
{
for(i=0;i<n;i++) //首先我把c中元素都赋为3.
c[i]=3;
k=0;sum=0;e=0;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
scanf("%d",&b[i]);
sort(a,n,c); //第一次进行排序。
sort(b,n,c);
for(i=0;i<n;i++) //在同一级别的能赢的就一定赢下来。
{
if(a[i]>b[i]) //赢了后c[i]=1,a[i]=-1,b[i]=-1,e用来记录同一级别赢得马的个数。
{
c[i]=1;
a[i]=-1;
b[i]=-1;
e++;
}
}
sort(a,n,c); //第二次排序,把那些赢得马排到后面去。
sort(b,n,c);
for(i=0;i<n-e;i++) //剩下的马,田忌的马都是小于或等于齐王的马。所以田忌的马能赢齐王的马就尽量赢。
{ //不能赢得我就尽量平。
m=0;
for(j=0;j<n-e;j++)
{
if(b[j]==-1)
continue;
if(a[i]>b[j])
{
c[i]=1;
b[j]=-1;
m=1; //这里m是,我赢了齐王得马,就不必去平他的马。
break;
}
}
for(j=0;j<n-e;j++)
{
if(m)
break;
if(b[j]==-1)
continue;
if(a[i]==b[j])
{
c[i]=0;
b[j]=-1;
break;
}
}
}
for(i=0;i<n;i++) //剩下的马都输了,我记为-1.
if(c[i]>1)
c[i]=-1;
for(i=0;i<n;i++) //求赢得的总钱。
{
if(c[i]==1)
sum+=200;
if(c[i]==-1)
sum-=200;
}
printf("%ld\n",sum);
}
return 0;
}
//我测试了许多数据,都是对的,但肯定有组过不了,应该哪里还有漏洞,欢迎各位大侠帮忙纠错,或者发表你的看法,什么意见都欢迎。你也可以把好算法沾上去,互相讨论,主要帮我看看哪错了,我将不胜感激。