题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2058
题目要求:
给出1，2，3，......，N，给定一个和，求出所有子序列区间的可能。
如在句子：1，2，3，4，5，6，7，8，9，10 中，找出子序列之和为9的所有区间。
即输入（N为10，M为9）
然后输出：[2，4]，[4，5]，[9，9].
----> 。。2+3+4=9 ~4+5=9.。9=9
image.png
做题思路:
这里以N为10，M为9为例
[1，2，3，4，5，6，7，8，9，10]
不难看出结果会是[2,4],[4,5],[9,9]，具体怎么求出来呢，最开始我是暴力算法的，即列出所有可能
暴力算法的代码:
#include "stdio.h"
int main() {
int n,m;
while(scanf("%d %d",&n,&m) == 2 && (n||m)) {
int sum = 0,count = 0;
int i;
for(i = 1;i <= m,i <= n;i++) {
sum += i;
if(sum == m) {
printf("[%d,%d]\n",i-count,i);
i = i - count;
sum = 0;
count = 0;
}
else if(sum < m) {
count++;
}
else {
i = i - count;
sum = 0;
count = 0;
}
}
}
}
Time Limit Exceeded。。。超时了。。。
很明显验证了暴力是解决不了所有问题的。
所以我猜测肯定有什么公式，但是我想不出来，在百度上一查，才知道使用等差数列求和公式
等差求和公式:
image.png
Sn=(a1+aN)n/2
=(a1+a1+d(n-1))n/2
=a1n+d(n-1)n/2;
这里d为1，即Sn = a1n+(n-1)n/2
不难得到n = ✔2*Sn，求出n的最小范围
image.png
在这里可以缩小n的范围，即项数的最小范围，
比如m = 6，则通过n <= ✔2m 可以求得n<=3，即有三种可能。
当n=3时，通过求和公式可得 a1=1，再通过求和公式可得Sn = 6符合条件，输出。（第一种情况）
.
.
.
等差求和算法的代码:
#include<stdio.h>
#include<math.h>
int main()
{
int n,m,l;
while(scanf("%d%d",&n,&m)>0&&n+m!=0)
{
int len;
for(len=(int)pow(2.0*m,0.5);len>=1;len--)
{
l=(2*m/len-len+1)/2;
if(len*(len+2*l-1)/2==m)
printf("[%d,%d]\n",l,l+len-1);
}
printf("\n");
}
}
很是难受，因为时间超时多花了两个小时。。。
