let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

KPLANK - Bán dừa

solution.md

Gọi \(A[i]\) là dãy input.

Do ta chỉ có thể cắt ngang theo một cạnh của tấm ván, kết quả của bài toán là một trong các giá trị \(A[i]\).

Giả sử đoạn \(A[l]\) đến \(A[r]\) có tấm ván ngắn nhất là \(A[i]\), ta có thể cắt một tấm ván vuông cạnh \(A[i]\) nếu \(r-l+1 \ge A[i]\).

Từ nhận xét trên, ta có thể giải bài toán dùng 2 vòng lặp (code n2.cpp).

Để giảm độ phức tạp thuật toán về \(O(N)\), gọi \(L[i]\) là số nhỏ nhất sao cho \(A[i]\) là min trong đoạn \(A[L[i]]\) đến \(A[i]\). Tương tự, \(R[i]\) là số lớn nhất sao cho \(A[i]\) là min trong đoạn \(A[i]\) đến \(A[R[i]]\). Khi đó, ta có thể cắt một tấm ván vuông dài \(A[i]\) nếu \(R[i] - L[i] + 1 \ge A[i]\).

\(L\) và \(R\) được tìm bằng stack.

Duyệt \(i\) từ 1 đến N, để tìm \(L[i]\) ta sẽ lặp \(j\) từ \(i\) về 1, dừng khi tìm được \(A[j] < A[i]\), ta có \(L[i] = j + 1\).

Nhận xét: ta có thể bỏ đi những giá trị ở giữa \(A[i]\) và \(A[j]\) trong lần duyệt sau.

Chứng minh: xét \(k > i\), nếu \(A[i] < A[k]\) thì việc lặp để tìm \(L[k]\) sẽ dừng tại \(i\) hoặc sớm hơn. Ngược lại, nếu \(A[i] \ge A[k]\), có thể bỏ qua những giá trị \(z, j < z < i\), do \(A[z] \ge A[i] \implies A[z] \ge A[k]\).

Từ nhận xét trên, ta lưu mảng \(S\) chứa những chỉ số cần duyệt. Khi duyệt, ta so sánh \(A[i]\) với \(A[last]\) (\(last\) là phần tử cuối cùng của \(S\)), nếu \(A[last] \ge A[i]\) thì xóa \(last\) ra khỏi \(S\). Dừng khi tìm được \(A[last] < A[i]\) hoặc mảng \(S\) đã rỗng. Sau đó thêm \(i\) vào cuối mảng \(S\).

Để tìm \(R\) ta duyệt từ \(n\) về 1 và làm tương tự. Code n.cpp cài đặt thuật toán này.

Xem thêm về kĩ thuật này ở Kĩ thuật sử dụng Deque tìm Min/Max trên đoạn tịnh tiến.

n2.cpp
Open in Github • Download 
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector<int> a(n);
    for (int &x: a) cin >> x;

    int result = 1;
    for (int i=0; i<n; i++) {
        int min_a = a[i];
        for (int j=i; j>=0; j--) {
            min_a = min(min_a, a[j]);
            if (i-j+1 >= min_a) result = max(result, min_a);
        }
    }
    cout << result << endl;
}
n.cpp
Open in Github • Download 
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector<int> a(n);
    for (int &x: a) cin >> x;
    
    vector<int> stack;
    vector<int> l(n);
    for (int i=0; i<n; i++) {
        while (!stack.empty() && a[stack.back()] >= a[i]) {
            stack.pop_back();
        }
        l[i] = stack.empty()? 0 : stack.back()+1;
        stack.push_back(i);
    }

    stack.clear();
    vector<int> r(n);
    for (int i=n-1; i>=0; i--) {
        while (!stack.empty() && a[stack.back()] >= a[i]) {
            stack.pop_back();
        }
        r[i] = stack.empty()? n-1 : stack.back()-1;
        stack.push_back(i);
    }

    int result = 1;
    for (int i=0; i<n; i++) {
        if (a[i] <= r[i] - l[i] + 1) {
            result = max(result, a[i]);
        }
    }
    cout << result << endl;
}
Comments