大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
The sum problem
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 24299 Accepted Submission(s): 7247
Problem Description
Given a sequence 1,2,3,……N, your job is to calculate all the possible sub-sequences that the sum of the sub-sequence is M.
Input
Input contains multiple test cases. each case contains two integers N, M( 1 <= N, M <= 1000000000).input ends with N = M = 0.
Output
For each test case, print all the possible sub-sequence that its sum is M.The format is show in the sample below.print a blank line after each test case.
Sample Input
20 10
50 30
0 0
Sample Output
[1,4]
[10,10]
[4,8]
[6,9]
[9,11]
[30,30]
刚看到这道题，开始想将1开头的子序列找完，然后是2，依次向下找，这里我们可以选择一直找到n，但是会超时，如果选择找到某个最大的介于1到n之间的数，那么我们首先要计算那个介于1到n之间的最大的数，发现无法计算。我们可以选择另一条思路，先算出子序列的最大长度，既然是从1到n的序列，我们可以根据等差数列计算，既然是最大长度，那么一定是从1开始（数字选择的越小，使用的数字越多，长度就越长），根据长度来计算子序列，如图所示
代码如下
#include<stdio.h>
#include<math.h>
int main() {
long long n,m,i,j,s = 0;
scanf(“%lld%lld”,&n,&m);
while(n != 0 && m != 0) {
if(n == 0 || m == 0)
return 0;
for(i = sqrt(2 * m); i > 0; i–) {
s = m / i – (i – 1) / 2;
if(s + i – 1 <= n && (s + s + i-1) * i == 2 * m) //防止（s+s+i-1）*i不等于2m，可能由于s的值在计算时，是约等的。
//对于s + i -1 <=n 一定要判断，因为如果输入的n值很小，
//但是m值很大，（2m）的开平方，可能大于n，如n=5，m=30
printf(“[%lld,%lld]\n”,s,s + i – 1);
}
printf(“\n”);
scanf(“%lld%lld”,&n,&m);
}
return 0;
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/186562.html原文链接：https://javaforall.net
