#include <stdio.h> int main() { int n; scanf("%d", &n);
int i, j, k, sum;
for (i = 1; i < n; i++) {
for (j = i + 1; j < n; j++) {
sum = 0;
for (k = i; k <= j; k++) {
sum += k;
}
if (sum == n) {
printf("%d %d\n", i, j);
break;
}
}
}
return 0;
}
共 9 条回复
@root 没看到
@CPP 单走一个6，话说你看到新初一的c++集训班没
谢谢
普通版：
优化遍历范围：
剪枝版：
二分版：
累加版：
这些代码可以参考一下。
漏了一个方法，也是 的时间复杂度，就是你枚举左端点后再枚举右端点，定义一个变量累加右端点。
总之，你需要自己思考一些冗余的情况，将其排除，从而降低时间复杂度。
如果你看不懂的话 @CPP
你的时间复杂度太高了，达到了 ，这个时间复杂度只能完成 左右的数据范围，而这题数据范围是 ，你只能使用 的时间复杂度过掉，如果你卡常的话也只能过 。
所以，你的代码中，第一个循环其实不用枚举这么大， 就行了，其次，你只需要枚举左端点 ，右端点 或者长度 ，然后运用等差数列求和公式： 即可，时间复杂度从 降到了 ，虽然常数可以省去但是节约了近 的时间。
然后我们可以继续优化代码，左端点是一定的，那么右端点越大，总和就越大，所以当总和大于 的时候，我们可以直接退出循环。但对于这道题来说这个优化没太大用处，但是当 的时候就有显著的作用。
如果 时，上述两种办法都会超时，所以我们考虑二分答案。
首先枚举左端点，然后二分右端点，当总和大于 时就把右端点放到左边查找，当总和小于 时，就把右端点往右移，直到找到唯一一个值，然后再验证答案是否正确。之间复杂度为 。