为什么是时间超限???

T001 2024-08-23 10:01:11 3

#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;

}

{{ vote && vote.total.up }}

共 9 条回复

CPP 刷题王

@root 没看到

root 站长

@CPP 单走一个6,话说你看到新初一的c++集训班没

T001

谢谢

T001
T001
CPP 刷题王

普通版:

    for (int a = 1; a <= n; a++) {
        for (int b = a + 1; b <= n; b++) {
            if ((a + b) * (b - a + 1) / 2 == n) {
                cout << a << ' ' << b << endl;
                break;
            }
        }
   }

优化遍历范围:

    int k = ceil(n / 2.0);
    for (int a = 1; a <= k; a++) {
        for (int b = a + 1; b <= k; b++) {
            if ((a + b) * (b - a + 1) / 2 == n) {
                cout << a << ' ' << b << endl;
                break;
            }
        }
    }

剪枝版:

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int k = ceil(n / 2.0);
    for (int a = 1; a <= k; a++) {
        for (int b = a + 1; b <= k; b++) {
            if ((a + b) * (b - a + 1) / 2 > n)
                break;
            if ((a + b) * (b - a + 1) / 2 == n) {
                cout << a << ' ' << b << endl;
                break;
            }
        }
    }
    return 0;
}

二分版:

    int k = ceil(n / 2.0);
    for (int a = 1; a <= k; a++) {
        int l = a, r = k;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if ((a + mid) * (mid - a + 1) / 2 > n)
                r = mid - 1;
            else
                l = mid;
        }
        if ((a + l) * (l - a + 1) / 2 == n)
            cout << a << ' ' << l << endl;
    }

累加版:

int k = ceil(n / 2.0);
for (int a = 1, sum; a <= k; a++) {
	sum = a;
	for (int b = a + 1; sum <= n; b++) {
		sum += b;
		if (sum == n) {
			cout << a << " " << b << endl;
			break;
		}
	}
}

这些代码可以参考一下。

CPP 刷题王

漏了一个方法,也是 的时间复杂度,就是你枚举左端点后再枚举右端点,定义一个变量累加右端点。

CPP 刷题王

总之,你需要自己思考一些冗余的情况,将其排除,从而降低时间复杂度。

如果你看不懂的话 @CPP

CPP 刷题王

你的时间复杂度太高了,达到了 ,这个时间复杂度只能完成 左右的数据范围,而这题数据范围是 ,你只能使用 的时间复杂度过掉,如果你卡常的话也只能过

所以,你的代码中,第一个循环其实不用枚举这么大, 就行了,其次,你只需要枚举左端点 ,右端点 或者长度 ,然后运用等差数列求和公式: 即可,时间复杂度从 降到了 ,虽然常数可以省去但是节约了近 的时间。

然后我们可以继续优化代码,左端点是一定的,那么右端点越大,总和就越大,所以当总和大于 的时候,我们可以直接退出循环。但对于这道题来说这个优化没太大用处,但是当 的时候就有显著的作用。

如果 时,上述两种办法都会超时,所以我们考虑二分答案。

首先枚举左端点,然后二分右端点,当总和大于 时就把右端点放到左边查找,当总和小于 时,就把右端点往右移,直到找到唯一一个值,然后再验证答案是否正确。之间复杂度为