关于贪心
查看原帖
关于贪心
480934
xqqQwQ_楼主2021/9/11 07:57

此题为什么不能贪心

统计出任意两个点上抛物线经过的点的个数,每次取最大的,然后把其他线上已被经过的点删掉,重复直到所有点都被经过

30分代码

#include<bits/stdc++.h>

using namespace std;

struct lines
{
	int num;
	bool sf[19];	
};

lines li[1001];

double ah[20][2];

bool cmp(lines a,lines b)
{
	return a.num>b.num;
}

int main()
{
	//freopen("angrybirds.in","r",stdin);
	//freopen("angrybirds.out","w",stdout);
	int t;
	cin>>t;
	while(t--)
	{
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>ah[i][0]>>ah[i][1];
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(i>=j) 
				{
					li[(i-1)*n+j].num=-999;
					continue;
				}
				double a,b;
				double x1=ah[i][0],y1=ah[i][1],x2=ah[j][0],y2=ah[j][1];
				a=(y1-y2*x1/x2)/(x1*(x1-x2));
				b=(y1-a*x1*x1)/x1;
				if(a>=0) 
				{
					li[(i-1)*n+j].num=-999;
					continue;
				}
				bool flag=0;
				for(int k=1;k<j;k++)
				{
					if(k==i) continue;
					if(a*ah[k][0]*ah[k][0]+b*ah[k][0]==ah[k][1]) 
					{
						flag=1;
						break;
					}
				}
				if(flag)
				{
					li[(i-1)*n+j].num=-999;
					continue;
				}
				li[(i-1)*n+j].sf[i]=1;
				li[(i-1)*n+j].sf[j]=1;
				li[(i-1)*n+j].num=2;
				for(int k=j+1;k<=n;k++)
				{
					if(ah[k][0]*ah[k][0]*a+b*ah[k][0]==ah[k][1]) 
					{
						li[(i-1)*n+j].num++;
						li[(i-1)*n+j].sf[k]=1;
					}
				}
			}
		}
		int ahh=n;
		int cnt=0;
		while(ahh>0)
		{
			sort(li+1,li+n*n+1,cmp);
			if(li[1].num<=0)
			{
				cnt+=ahh;
				break;
			}
			ahh-=li[1].num;
			li[1].num=-999;
			for(int i=1;i<=n;i++)
			{
				if(li[1].sf[i])
				{
					for(int j=2;j<=n*n;j++)
					{
						if(li[j].sf[i])
						{
							li[j].num--;
							li[j].sf[i]=0;
						}
					}
					li[1].sf[i]=0;
				}
			}
			cnt++;
		}
		cout<<cnt<<endl;
	}
	return 0;
}
2021/9/11 07:57
加载中...