Goffi and Squary Partition Time Limit: / MS (Java/Others) Memory Limit: / K (Java/Others)
Total Submission(s): Accepted Submission(s): Problem Description
Recently, Goffi is interested in squary partition of integers. A set X of k distinct positive integers is called squary partition of n if and only if it satisfies the following conditions:
[ol]
the sum of k positive integers is equal to n
one of the subsets of X containing k− numbers sums up to a square of integer.
[/ol]
For example, a set {, , , } is a squary partition of because + + + = and + + = = × . Goffi wants to know, for some integers n and k, whether there exists a squary partition of n to k distinct positive integers. Input
Input contains multiple test cases (less than ). For each test case, there's one line containing two integers n and k (2≤n≤200000,2≤k≤30). Output
For each case, if there exists a squary partition of n to k distinct positive integers, output "YES" in a line. Otherwise, output "NO". Sample Input Sample Output
NO
YES
YES
题意：输入整数n和k，要求把n分成k个数之和的形式，其中存在k-1个数之和为一个完全平方数，而且这k个数各不相同。
分析： 我们尝试枚举那个完全平方数 S,然后看能否将他拆分为 K-1 个数,并且不用到N-S 这一步可以用贪心+一次调整来搞定。为了保证 K-1 个数都不同,我们尝试尽量
用 1,2,3...这些连续自然数来构造,如果 N-S 出现在这些数中,那么将 N-S 移除,再新加一个数。最后一个数由S-sum（1~k-2）(包括调整过的)来得到。
- 1.如果sum值大于S值，可以分成两种情况来看
1.1 前k-2个数中不存在N-S，那么原数列为1，2，3，....，k-2，其中的和大于等于S值，且最小的数为1，没有剩余的空间减少这k-2个数的和
1.2 前k-2个数中存在N-S，设x等于N-S那么原数列为1，2，....x-1，x+1，.....，k-1，其中多出来的空间为避免N-S，同样不存在剩余空间减少和
- 2.如果倒数最后一个数在前面k-2个数中出现，由上面结论可知，必定存在冲突，且无法调整
- 3.如果倒数最后一个数与N-S相等，那么可以使得倒数第一个数-1和倒数第二个数+1，这样的调整代价是最小的，如果这样的处理方式仍存在冲突，就为错
#include <cstdio>
using namespace std;
int pnt[],top;
int n,k;
bool check(int x)
{
int sum=,top=;
int r=n-x,cc=,cnt=;
pnt[top++]=;
for(int i=; i<k-; i++)
{
cc++;
if(cc==r) cc++;
pnt[top++]=cc;
sum+=cc;
}
if(sum>=x) return false;
pnt[top]=x-sum;
if(pnt[top]<=pnt[top-]) return false;
if(pnt[top]==r)
{
if(pnt[top-]+>=pnt[top]-) return false;
}
return true;
}
int main()
{
while(~scanf("%d%d",&n,&k))
{
int flag=;
for(int i=; i<=; i++)
{
if(i*i>=n) break;
if(check(i*i))
{
printf("%d\n",i*i);
printf("YES\n");
flag=;
break;
}
}
if(flag) continue;
printf("NO\n");
}
return ;
}