Hiểu bài toán

Bài toán yêu cầu tìm giá trị tối thiểu $x$ sao cho Cám có thể chọn một đoạn liên tiếp độ dài $k$ (gọi là đoạn Cám), và sau đó Tấm chỉ có thể chọn một đoạn liên tiếp độ dài $k$ khác đoạn Cám (các đoạn không được chung phần tử). Mục tiêu của Cám là làm cho tổng giá trị quà mà Tấm có thể nhận được là nhỏ nhất có thể. Nói cách khác, Cám sẽ chọn một đoạn để 'khóa' nó, và Tấm sẽ chọn đoạn còn lại có tổng giá trị lớn nhất. Cám muốn tác động lên sự lựa chọn của Tấm sao cho tổng giá trị lớn nhất đó là nhỏ nhất. Ta cần tìm giá trị nhỏ nhất này.

Formal hóa bài toán: Cho mảng $A$ gồm $n$ phần tử. Gọi $W[i]$ là tổng của $k$ phần tử liên tiếp bắt đầu từ $i$ ($1 \le i \le n-k+1$). Cám chọn một chỉ số $i$. Tấm được chọn chỉ số $j$ sao cho hai đoạn $[i, i+k-1]$ và $[j, j+k-1]$ không giao nhau. Cám muốn tối thiểu hóa giá trị: $\max{j \text{ không giao } i} W[j]$. Ta cần tính: $\min{i} ( \max_{j \text{ không giao } i} W[j] )$.

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

Cách Quy hoạch động và tiền xử lý mảng truy vấn

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG = -(1LL<<60);
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n,k; if(!(cin>>n>>k)) return 0;
    vector<int> a(n+1); for(int i=1;i<=n;i++) cin>>a[i];
    int m = n-k+1;
    vector<ll> w(m+1,0);
    ll s=0; for(int i=1;i<=k;i++) s+=a[i];
    w[1]=s;
    for(int i=2;i<=m;i++){ s+=a[i+k-1]-a[i-1]; w[i]=s; }

    vector<ll> pref(m+1,NEG), suf(m+2,NEG);
    for(int i=1;i<=m;i++) pref[i]=max(pref[i-1], w[i]);
    for(int i=m;i>=1;i--) suf[i]=max(suf[i+1], w[i]);

    ll ans = (1LL<<62);
    for(int i=1;i<=m;i++){
        ll leftMax  = (i-k>=1)? pref[i-k] : NEG;
        ll rightMax = (i+k<=m)? suf[i+k]   : NEG;
        ll tam = max(leftMax, rightMax);
        ans = min(ans, tam);
    }
    cout<<ans<<"\n";
}

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

Đây là cách tiếp cận trực tiếp dựa trên mô tả bài toán.

1. Tính mảng tổng trượt $W$: Duyệt mảng $A$ để tính tổng các đoạn liên tiếp độ dài $k$. Độ phức tạp $O(n)$.
2. Tạo mảng truy vấn:
   • pref[i]: lưu tổng lớn nhất của các đoạn nằm trong khoảng $[1, i]$.
   • suf[i]: lưu tổng lớn nhất của các đoạn nằm trong khoảng $[i, m]$. Độ phức tạp $O(n)$.
3. Với mỗi vị trí Cám chọn là đoạn $[i, i+k-1]$:
   • Các đoạn Tấm có thể chọn phải nằm hoàn toàn bên trái đoạn $i$ (tức là chỉ số đoạn $<= i-k$) hoặc hoàn toàn bên phải (chỉ số đoạn $>= i+k$).
   • Giá trị Tấm có thể đạt được lớn nhất là $\max(\text{leftMax}, \text{rightMax})$.
   • Cám muốn chọn $i$ để giá trị này là nhỏ nhất, nên ta duyệt qua tất cả $i$ và lấy min của các giá trị lớn nhất đó. Độ phức tạp tổng thể là $O(n)$ về thời gian và bộ nhớ.

Cách Quy hoạch động

#include <iostream>
#include <algorithm>
#include <climits>
#define ll long long
using namespace std;

const ll N = 1e6 + 17;
ll n, k, a[N], l[N], r[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;
    for (ll i = 1; i <= n; i++) cin >> a[i];

    ll c = 0;
    for (ll i = 1; i < k; i++) c += a[i];
    for (ll i = k; i <= n; i++) {
        c += a[i];
        c -= a[i - k];
        l[i] = max(l[i - 1], c);
    }

    c = 0;
    for (ll i = n; i > n - k + 1; i--) c += a[i];
    for (ll i = n - k + 1; i >= 1; i--) {
        c += a[i];
        c -= a[i + k];
        r[i] = max(r[i + 1], c);
    }

    ll ans = LLONG_MAX;
    for (ll i = 1; i <= n - k + 1; i++) {
        ans = min(ans, max(l[i - 1], r[i + k]));
    }

    cout << ans << endl;
    return 0;
}

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

Cách tiếp cận này cũng sử dụng ý tưởng tiền xử lý để trả lời truy vấn nhanh, nhưng cách tính mảng $l$ và $r$ được thực hiện cẩn thận dựa trên chỉ số của các đoạn.

1. Mảng $l[i]$: Lưu tổng lớn nhất của đoạn độ dài $k$ mà đoạn đó kết thúc tại vị trí $i$ của mảng $A$. Thực tế, đoạn kết thúc tại $i$ sẽ bắt đầu tại $i-k+1$. Mảng $l$ được tính bằng cách quét từ trái sang phải, cập nhật tổng trượt và lấy max.
2. Mảng $r[i]$: Lưu tổng lớn nhất của đoạn độ dài $k$ mà đoạn đó bắt đầu tại vị trí $i$ của mảng $A$. Mảng $r$ được tính bằng cách quét từ phải sang trái.
3. Khi Cám chọn đoạn bắt đầu tại $i$ (kết thúc tại $i+k-1$):
   • Các đoạn Tấm chọn phải kết thúc trước $i$ hoặc bắt đầu sau $i+k-1$.
   • Do đó, tổng lớn nhất Tấm có thể chọn là $\max(l[i-1], r[i+k])$.
   • Ta duyệt qua mọi $i$ để tìm giá trị nhỏ nhất. Lưu ý: Trong code mẫu, chỉ số $i$ duyệt trong vòng for cuối cùng là chỉ số bắt đầu của đoạn Cám.

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

Bài học kinh nghiệm

• Vấn đề có thể được chia thành 2 phần: (1) Tính tổng giá trị các đoạn liên tiếp độ dài $k$ (Sliding Window) và (2) Tìm max trên các đoạn không giao nhau (Tiền xử lý mảngPrefix/Suffix).
• Bài toán yêu cầu tìm giá trị nhỏ nhất trong các giá trị lớn nhất (Minimize the Max). Do đó, ta có thể duyệt qua từng khả năng chọn của Cám và tính giá trị Tấm có thể chọn được, sau đó lấy min.
• Các đoạn không giao nhau có thể được chia thành 2 tập hợp: nằm hoàn toàn bên trái và nằm hoàn toàn bên phải đoạn Cám đã chọn.

Lỗi thường gặp

• Sử dụng chỉ số sai: Khi tính tổng trượt, cần phân biệt rõ chỉ số của mảng $A$ và chỉ số của các đoạn (mảng $W$). Nếu chọn đoạn Cám bắt đầu tại $i$, các đoạn Tấm chọn phải nằm ở khoảng $[1, i-k]$ và $[i+k, m]$ (với $m = n-k+1$ là số lượng đoạn).
• Xử lý biên: Cần kiểm tra điều kiện $i-k \ge 1$ và $i+k \le m$ trước khi truy cập mảng Prefix/Suffix để tránh lỗi truy cập ngoài vùng nhớ.
• Kiểu dữ liệu: Tổng giá trị quà có thể lên tới $10^6 \times 10^6 = 10^{12}$, nên bắt buộc phải dùng long long (hoặc int64_t) để lưu trữ, tránh bị tràn số với int.