Tìm đoạn con ngắn nhất có tổng lớn hơn K

Bài này em code như v, prefixsum rồi duyệt trâu

void solve() {
        int n, k, s = 0;
        cin >> n >> k;
        vector<int> a(n + 1), f(n + 1);
        f[0] = 0;
        for (int i = 1; i <= n; ++i) {
                cin >> a[i];
                f[i] = f[i - 1] + a[i];
        }

        int _min = n;

        for (int i = n; i > 0; --i) {
                for (int j = i; j > 0; --j) {
                        if (f[i] - f[j] >= k)
                                _min = min(_min, i - j);
                }
        }

        cout << _min;
}

E bị TLE ở test cuối n = 500000
Có cách nào tối ưu hơn nữa ko ạ ?

Mảng không âm thì có thể co kéo chứ có số âm thì ko giải nhanh được.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?