我的思路是让田忌的马能够胜利的就去胜利。首先将两者的马速度由大到小排序,然后选取田忌的马来挨个对抗齐王的马,直到匹配到能够打败的对手。然后再匹配下一匹,以此类推,直到不再存在能打败对手的马。然后再用相同的方法匹配平手的马,最后计算出失败的马。
所以这样的思路哪里错了QAQ
(附:code)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,ans,cnt=1,s1;
int h1[100100],h2[100100],vis[100100];
int f[2002][2002];
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
// freopen("P1650_2.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&h1[i]);
for(int i=1;i<=n;++i)scanf("%d",&h2[i]);
sort(h1+1,h1+1+n,cmp);
sort(h2+1,h2+1+n,cmp);
while(cnt<n)
{
int flag=1;
s1=cnt;
for(int i=flag;i<=n;++i)
{
if(h1[cnt]>h2[i]&&(!vis[i]))
{
vis[i]=1;
++cnt;
ans+=200;
flag=i;
}
}
if(s1==cnt)break;
}
while(cnt<n)
{
int flag=0;
s1=cnt;
for(int i=1;i<=n;++i)
{
if(h1[cnt]==h2[i]&&(!vis[i]))
{
vis[i]=1;
++cnt;
flag=1;
}
if(flag)break;
}
if(s1==cnt)break;
}
printf("%d",ans-200*(n-cnt+1));
return 0;
}