Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1171 Accepted Submission(s): 402
/** 题意:给你k个数(各不相同的正整数),它们的和是n,问是否存在k-1个数的和是某个数的平方? 分析:我们假设其中k-1个数个数的平方为 m , m 应该不小于 k*(k-1)/2,不然就会有重复的 。 我们可以通过构造一个序列来判断是否满足条件。 */ #include <stdio.h> #include <math.h> #include <iostream> #include <algorithm> #include <string.h> #include <vector> using namespace std; typedef long long LL; int n,k; bool judge(int m){ int t = n-m, sum = (k-1)*k/2; if(sum>m) return false; ///k-1项最小都要 sum int count=0,x=0; for(int i=1;i<k-1;i++){ ///构造出一个序列包含剩下的序列中的 k - 2 项 x++; if(t==x) x++; count+=x; } int lastnum = n-count-t; ///剩下的序列中的第 k-1 个数 if(lastnum<=x) return false; ///如果最后一个数小于 x ,那么之前肯定存在过了 x++; if(t==x||t==x+1){ ///如果 t == x 或者 t==x+1 那么当 第k-1个数等于t 的时候我们无法通过改变前k-2 ///项的值令 lastnum != t 了,如果t更大一些,我们是可以通过改变 k-1这个序列的值 ///来让 lastnum != t 的. if(lastnum==t) return false; } return true; } int main() { while(scanf("%d%d",&n,&k)!=EOF){ bool flag = false; for(int i=1;i*i<n;i++){ int m = i*i; if(judge(m)){ flag = true; break; } } if(flag) printf("YES\n"); else printf("NO\n"); } return 0; }
原文:http://www.cnblogs.com/liyinggang/p/5630533.html