#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
你的时间复杂度太高了,达到了 ,这个时间复杂度只能完成 左右的数据范围,而这题数据范围是 ,你只能使用 的时间复杂度过掉,如果你卡常的话也只能过 。
所以,你的代码中,第一个循环其实不用枚举这么大, 就行了,其次,你只需要枚举左端点 ,右端点 或者长度 ,然后运用等差数列求和公式: 即可,时间复杂度从 降到了 ,虽然常数可以省去但是节约了近 的时间。
然后我们可以继续优化代码,左端点是一定的,那么右端点越大,总和就越大,所以当总和大于 的时候,我们可以直接退出循环。但对于这道题来说这个优化没太大用处,但是当 的时候就有显著的作用。
如果 时,上述两种办法都会超时,所以我们考虑二分答案。
首先枚举左端点,然后二分右端点,当总和大于 时就把右端点放到左边查找,当总和小于 时,就把右端点往右移,直到找到唯一一个值,然后再验证答案是否正确。之间复杂度为 。