http://acm.pku.edu.cn/JudgeOnline/problem?id=2287这是2004上海两道最简单的题之一,但我做这题时用了两个半小时,其实如果一开始就采用最后的算法的话也是15分钟就通过了.唉,首先是将田忌的马和齐王的马分别进行排序,然后在齐王的序列中找到田忌最快的马的位置,它之前有几匹马那田忌就至少输掉几场比赛,然后开始枚举最终输掉的场次,将田忌最慢的马与齐王最好的马比赛,剩下的马一一对应比赛,找出赢钱的最大值就可以了.我希望直接用算法找到最后的结果,想了2个多小时也没有结果,最后在问题规模不大的情况用了这样的方法.没办法啊.
程序如下:
#include<stdio.h>
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
int x,y;
x=*(int *)a;
y=*(int *)b;
if (x<y)
return 1;
else if (x>y)
return -1;
else return 0;
}
int main()
{
int i,j,k,s,x,n,t[1000],q[1000];
scanf("%d",&n);
while (n!=0)
{
for (i=0;i<n;i++)
scanf("%d",&t[i]);
for (i=0;i<n;i++)
scanf("%d",&q[i]);
qsort(t,n,sizeof(t[0]),cmp);
qsort(q,n,sizeof(q[0]),cmp);
for (i=0;t[0]<q[i] && i<n;i++);
for (s=-200*n;i<n;i++)
{
x=-i*200;
for (j=i,k=0;j<n;j++,k++)
{
if (t[k]>q[j])
x+=200;
else if (t[k]<q[j])
x-=200;
}
if (x>s)
s=x;
}
printf("%d\n",s);
scanf("%d",&n);
}
return 0;
}