HDU 4982 Goffi and Squary Partition

HDU 4982 Goffi and Squary Partition

題目鏈接：HDU 4982 Goffi and Squary Partition

題意：給出n和k，和為一個平方數的k-1個各不相同的數，在加上一個數（這個數也和k-1個數不同），他們總和等於n，求是否存在這樣的序列。

思路：枚舉平方數。構造最小的序列當然從1開始。

AC代碼：

#include
int k,n;
bool judge(int sum,int lef)//sum前k-1項和，lef剩下。sum+lef=n
{
	if(lef==0 || 2*sum<(k-1)*k)
			return false;
	if(sum==1 && lef==1)
		return false;
	int x,ss;//ss為前k-2項和
	ss=0,x=0;
	for(int i=0;ix
	x++;//改變k-2項的值
	//前k-2都是緊密排列的，如果(k-1),(k-2),lef相等，至少要移動2個位置才能滿足要求。
	if(temp==x && temp==lef)//k-2項+1等於k-1項等於lef
		return false;
	if(temp==x+1 && temp==lef)//k-2項+2等於k-1項等於lef
		return false;
	return true;
}
int main()
{
	int i;
	int lef;

	while(scanf("%d %d",&n,&k)!=EOF)
	{
		int flag=0;
		for(i=1;i*i<=n;i++)
		{
			lef=n-i*i;
			if(judge(i*i,lef))
				break;
		}
		if(i*i<=n)
			printf("YES\n");
		else
			printf("NO\n");
	}
return 0;
}