错误的贪心策略?
查看原帖
错误的贪心策略?
159959
虫洞吞噬者楼主2021/9/18 15:49

我的思路是让田忌的马能够胜利的就去胜利。首先将两者的马速度由大到小排序,然后选取田忌的马来挨个对抗齐王的马,直到匹配到能够打败的对手。然后再匹配下一匹,以此类推,直到不再存在能打败对手的马。然后再用相同的方法匹配平手的马,最后计算出失败的马。

所以这样的思路哪里错了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;
}
2021/9/18 15:49
加载中...