hdu 4982 贪心构造序列

时间:2025-01-20 15:35:50

http://acm.hdu.edu.cn/showproblem.php?pid=4982

给定n和k,求一个包含k个不相同正整数的集合,要求元素之和为n,并且其中k-1的元素的和为完全平方数

枚举平方数,从1开始构造余下序列(贪心),需要特判最后剩下的一个数是否在之前的序列或者和n-m*m相同,然后就是++--不断判断能否返回true
or false

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define clr0(x) memset(x,0,sizeof(x))
typedef long long LL;
const int maxn = 200001;
int n,k;
bool ok(int m,int s,int kk)
{
if(!s)
return false;
int i = 1;
kk--;
while(kk--){
if(i == s)
++i;
if(m <= i)
return false;
m -= i;
++i;
}
while(1){
if(m < i)
return false;
if(m != s)
return true;
++i,--m;
}
return false;
}
int main() {
// int _;RD(_);while(_--){
// ;
// }
while(~RD2(n,k)){
int m = sqrt(n);
bool flag = false;
while(m >= 1){
if(ok(m*m,n - m*m,k - 1)){
flag = true;
break;
}
m--;
}
if(flag)
puts("YES");
else
puts("NO");
}
return 0;
}