Hiểu bài toán

Bài toán yêu cầu tìm giá trị x nhỏ nhất sao cho Hermione có thể chọn một đoạn liên tiếp gồm k phần thưởng, để sau đó Harry không thể chọn được một đoạn liên tiếp k phần thưởng nào khác (trong số còn lại) có tổng giá trị lớn hơn x. Nói cách khác, Hermione muốn 'khóa' các đoạn Harry có thể chọn sao cho đoạn có tổng giá trị lớn nhất mà Harry chọn được là nhỏ nhất có thể. Hermione chỉ quan tâm đến việc giảm thiểu 'chiến lợi phẩm' của Harry chứ không quan tâm đến tổng của cô ấy.

Các cách tiếp cận

Cách Brute Force

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // Tính tổng tiền tố để tính tổng đoạn nhanh
    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + a[i];
    }

    long long global_min_max = LLONG_MAX;

    // Duyệt qua tất cả các lựa chọn của Hermione
    for (int i = 0; i <= n - k; i++) {
        // Hermione chọn đoạn [i, i+k-1]
        // Tìm đoạn tổng lớn nhất mà Harry có thể chọn
        long long max_harry = -1;

        // Kiểm tra các đoạn bên trái của Hermione
        for (int j = 0; j <= i - k; j++) {
            long long sum = prefix[j + k] - prefix[j];
            if (sum > max_harry) max_harry = sum;
        }

        // Kiểm tra các đoạn bên phải của Hermione
        for (int j = i + k; j <= n - k; j++) {
            long long sum = prefix[j + k] - prefix[j];
            if (sum > max_harry) max_harry = sum;
        }

        if (max_harry != -1) {
            global_min_max = min(global_min_max, max_harry);
        }
    }

    cout << global_min_max << endl;
    return 0;
}

• Time Complexity: O(n*k) hoặc O(n^2)
• Space Complexity: O(n)

Cách tiếp cận này thử tất cả các cách chọn k phần thưởng liên tiếp của Hermione. Với mỗi cách chọn, nó lặp lại các đoạn còn lại để tìm đoạn có tổng lớn nhất mà Harry có thể chọn. Do lặp lồng nhau nên độ phức tạp rất cao, không khả thi với n lớn.

Cách Sử dụng mảng tổng trước và tối ưu hóa (Prefix Arrays)

#include <bits/stdc++.h>
using namespace std;
long long a[1000001], p[1000001], s[1000001], pref[1000001], suff[1000001];
long long n, k, i, res = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
    }
    // Tính tổng của mọi đoạn có độ dài k
    for (i = 1; i + k - 1 <= n; i++)
        s[i] = p[i + k - 1] - p[i - 1];

    // pref[i] là tổng lớn nhất của các đoạn từ 1 đến i
    for (i = 1; i <= n; i++)
        pref[i] = max(pref[i - 1], s[i]);

    // suff[i] là tổng lớn nhất của các đoạn từ i đến n
    for (i = n - k + 1; i >= 1; i--)
        suff[i] = max(suff[i + 1], s[i]);

    // Duyệt qua lựa chọn của Hermione
    for (i = 1; i + k - 1 <= n; i++) {
        long long best = 0;
        // Đoạn Harry chọn nằm bên trái Hermione
        if (i - k >= 1) best = max(best, pref[i - k]);
        // Đoạn Harry chọn nằm bên phải Hermione
        if (i + k <= n - k + 1) best = max(best, suff[i + k]);
        res = min(res, best);
    }
    cout << res;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Approach này chia thành các bước:

1. Tính tổng tiền tố (prefix sum) để tính tổng đoạn liên tiếp trong O(1).
2. Tính tổng của tất cả các đoạn độ dài k, lưu vào mảng s.
3. Xây dựng 2 mảng phụ:
   • pref[i]: tổng lớn nhất của các đoạn nằm trong khoảng [1, i].
   • suff[i]: tổng lớn nhất của các đoạn nằm trong khoảng [i, n].
4. Với mỗi lựa chọn của Hermione tại vị trí i:
   • Các đoạn Harry có thể chọn nằm bên trái sẽ nằm trong khoảng [1, i-k]. Tổng lớn nhất ở đây là pref[i-k].
   • Các đoạn Harry có thể chọn nằm bên phải sẽ nằm trong khoảng [i+k, n]. Tổng lớn nhất ở đây là suff[i+k].
   • Harry sẽ chọn max của hai bên đó.
   • Hermione muốn tìm min của các max này.

Ví dụ minh họa: Harry có thể chọn đoạn [1, 2] hoặc [3, 4] (giả sử k=2). Nếu Hermione chọn [3, 4], Harry chỉ được chọn bên trái [1, 2]. Nếu Hermione chọn [1, 2], Harry chỉ được chọn bên phải [3, 4].

Công thức quan trọng: Harry's max = max( max tổng bên trái, max tổng bên phải ). Hermione's goal = min (over all her choices) of Harry's max.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Việc Hermione chọn một đoạn k liên tiếp sẽ chia dãy ban đầu thành 2 phần độc lập bên trái và bên phải (hoặc 1 phần nếu chọn đầu hoặc cuối). Harry sẽ chọn đoạn có tổng lớn nhất trong 2 phần còn lại.
• Sử dụng mảng prefix và suffix (mảng tiền tố và hậu tố) để lưu tổng lớn nhất của các đoạn k từ trái sang phải và từ phải sang trái. Điều này giúp truy vấn tổng lớn nhất trong một dải bất kỳ trong thời gian O(1) sau khi xử lý trước O(n).
• Bài toán quy về: Với mỗi vị trí i Hermione chọn, Harry sẽ lấy max(pref[i-k], suff[i+k]). Hermione cần tìm min của các giá trị này.

Lỗi thường gặp

• Lỗi chỉ số mảng (off-by-one errors) khi tính toán các đoạn k, đặc biệt là khi chia đôi mảng cho Harry. Cần chú ý khoảng cách giữa 2 đoạn là k (ví dụ: Hermione chọn đoạn kết thúc tại i, Harry chọn đoạn bắt đầu tại i+k).
• Xử lý các trường hợp đặc biệt: Hermione chọn đoạn đầu tiên (không có phần bên trái), Hermione chọn đoạn cuối cùng (không có phần bên phải).
• Kiểu dữ liệu: Tổng giá trị có thể lên tới 10^14 (n=10^5, a_i=10^9), cần dùng long long.