Hướng dẫn giải của Chồng Gạch


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, Nguyenminhkhoi, ducanhkingofcoder, orzitzzang

Hiểu bài toán

Bài toán yêu cầu tìm độ cao tối đa của một chồng gạch có N viên. Mỗi viên gạch có độ cứng ai, nghĩa là viên gạch đó có thể chịu được tối đa ai viên gạch đặt lên trên nó. Để xây dựng một chồng gạch có k viên (từ dưới lên trên), tổng số viên gạch ở các vị trí từ 1 đến k-1 (vị trí từ dưới lên) phải đủ để chịu tải trọng của các viên gạch phía trên. Cụ thể, viên gạch ở vị trí i (từ dưới lên, i = 1 là đáy) cần có độ cứng >= (k - i). Tuy nhiên, ta có thể chọn và sắp xếp lại các viên gạch. Câu hỏi trở thành: Với tập hợp N số a_i, ta có thể chọn ra một số k và tạo thành một dãy k số thỏa mãn điều kiện trên hay không, và tìm k lớn nhất.

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

Cách Sắp xếp và Thử nghiệm (Binary Search)
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> a;

bool check(int k) {
    // Chọn k viên gạch có độ cứng lớn nhất
    // Giả sử a đã được sắp xếp tăng dần
    // Chúng ta cần kiểm tra xem k viên cuối có thỏa mãn không
    for (int i = 0; i < k; ++i) {
        // Viên gạch thứ i từ dưới lên (dễ nhất) trong số k viên này là a[n - k + i]
        // Yêu cầu: a[n - k + i] >= (k - 1 - i)
        if (a[n - k + i] < (k - 1 - i)) return false;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a.begin(), a.end());

    int low = 0, high = n, ans = 0;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (check(mid)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    cout << ans << endl;
    return 0;
}
  • Time Complexity: O(N log N)
  • Space Complexity: O(N)

Cách tiếp cận này sử dụng Binary Search để tìm độ cao tối đa k. Với mỗi giá trị k ta kiểm tra xem có thể tạo được chồng gạch cao k không. Để kiểm tra, ta chọn k viên gạch có độ cứng lớn nhất (sau khi sắp xếp tăng dần). Giả sử các viên này là a[n-k], ..., a[n-1]. Ta gán viên gạch có độ cứng nhỏ nhất trong số này (a[n-k]) cho vị trí đáy, viên tiếp theo cho vị trí thứ 2... Kiểm tra điều kiện a[n-k+i] >= k-1-i với mọi i từ 0 đến k-1. Nếu thỏa mãn thì k hợp lệ.

Cách Sắp xếp và Duyệt tuyến tính (Greedy)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a.begin(), a.end());

    // Nếu viên gạch lớn nhất có thể làm đáy cho cả chồng N viên
    // (tức là a[n-1] >= N-1) và đủ gạch thì đáp án là N.
    // Tuy nhiên, điều kiện này chỉ cần thiết nếu ta dùng hết gạch.
    // Thuật toán chung:

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        // a[i] là độ cứng của viên gạch thứ i (từ nhỏ đến lớn)
        // Nếu ta dùng viên này làm 1 phần của chồng gạch, 
        // số viên gạch có thể đặt lên trên nó phải >= 0.
        // Giả sử ta đang xây một chồng có tổng cộng (ans + 1) viên.
        // Viên gạch này sẽ đóng góp vào độ cao.
        // Điều kiện: a[i] >= ans (vì ans là số viên trên nó nếu nó là viên mới thêm vào)
        // Hay suy nghĩ khác: Ta có thể xếp được ans viên.
        // Khi xét viên gạch tiếp theo a[i], ta có thể tăng độ cao lên 1 nữa không?
        // Nếu a[i] >= ans, ta có thể xếp thêm 1 tầng (đặt viên này lên trên)
        // Hoặc suy nghĩ: Liệt kê các viên gạch thỏa mãn a[i] >= số lượng viên gạch còn lại trong chồng.
        // Thuật toán đúng trong các submission:
        // Sắp xếp tăng dần.
        // Duyệt từ đầu, nếu a[i] >= số lượng viên gạch hiện tại đang xét (hoặc số lượng viên gạch nhỏ hơn/ bằng nó)

        // Code mẫu từ solution:
        // int d = 0;
        // for(int i=1; i<=n; i++) if(d <= a[i]) d++;
        // Logic: d là độ cao hiện tại. 
        // Nếu viên gạch a[i] có thể chịu được d viên gạch phía trên (tức a[i] >= d),
        // ta có thể đặt nó vào đáy của một chồng gạch mới hoặc bổ sung vào.
        // Nhưng thực tế thuật toán này đang đếm số lượng viên gạch thỏa mãn a[i] >= count.
        // Nó tìm số lượng viên gạch có thể tạo thành một nhóm mà ở đó viên thứ k (từ nhỏ đến lớn) có độ cứng >= k-1.

        // Code tối ưu nhất (từ Solution 2):
    }

    // Implementation từ Solution 2:
    int d = 0;
    for(int i = 0; i < n; i++) {
        if(d <= a[i]) {
            d++;
        }
    }
    cout << d;
    return 0;
}
  • Time Complexity: O(N log N)
  • Space Complexity: O(N)

Thuật toán này sắp xếp các viên gạch theo độ cứng tăng dần. Sau đó, nó duyệt qua các viên gạch và đếm số lượng viên gạch có thể tạo thành một chồng gạch hợp lệ. Biến d đếm số lượng viên gạch đã chọn được. Với mỗi viên gạch a[i], nếu d <= a[i] (tức là viên gạch này có độ cứng đủ để chịu tải d viên gạch khác), ta có thể đưa nó vào bộ sưu tập. Nếu d là số lượng viên gạch ta đã có, thì viên gạch mới này có thể đặt ở vị trí thứ d+1 (từ dưới lên) trong một chồng gạch mới, và điều kiện để nó không bị vỡ là a[i] >= d. Nếu thỏa mãn, ta tăng d lên 1. Cuối cùng d chính là độ cao tối đa.

Cách Sắp xếp Giảm dần và Xây dựng từ trên xuống
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    // Solution 3: Sắp xếp giảm dần
    sort(a.rbegin(), a.rend());

    // Logic: Giả sử viên gạch cứng nhất làm đáy.
    // Ta cần tìm độ cao h.
    // Viên gạch cứng nhất (a[0]) cần chịu h-1 viên.
    // Viên gạch thứ 2 (a[1]) cần chịu h-2 viên...
    // Viên gạch thứ i (từ 0) cần chịu h-1-i viên.
    // Ta có thể thử greed: Chọn các viên gạch mạnh nhất.
    // Hoặc duyệt:

    int h = a[0]; // Giả định độ cao ban đầu bằng độ cứng viên đầu tiên (hoặc n)
    int i = 1;
    for (; i < n; ++i) {
        if (h == 0) break;
        // Logic này hơi lạ: h = min(h - 1, a[i])
        // h ở đây có lẽ là "sức chịu tải còn lại" của viên gạch trước đó.
        // Thực ra đây là cách khác để tính độ cao.
    }

    // Code rõ ràng hơn:
    // Sắp xếp giảm dần.
    // Duyệt từ i = 0.
    // Giả sử độ cao bắt đầu bằng a[0] + 1? Không.
    // Thuật toán chính xác để giải thích:
    // Sắp xếp giảm dần.
    // Đặt h = a[0].
    // Duyệt i từ 1:
    //   Nếu a[i] >= h - 1 thì h = h - 1 (hoặc không thay đổi?)
    //   Thực ra: Viên thứ i có thể đặt ở vị trí h-1 nếu a[i] >= h-1.
    //   Nếu a[i] >= h-1, ta có thể giữ nguyên độ cao h (tức viên này có thể nằm ở vị trí h-1).
    //   Nhưng ta đang xét từ trên xuống.

    // Logic từ code mẫu:
    // h = arr[0];
    // for (i=1; i<n; i++) {
    //     if (h == 0) break;
    //     h = min(h - 1, arr[i]);
    // }
    // cout << i;
    // Giải thích:
    // arr[0] là lớn nhất, nó có thể làm đáy cho độ cao arr[0] + 1?
    // Không, h ở đây là độ cao tối đa có thể tạo ra tính đến thời điểm hiện tại.
    // Ban đầu h = arr[0] (vì viên này có thể chịu arr[0] viên -> chồng cao arr[0]+1).
    // Tuy nhiên, code tính i là số viên.
    // Hãy xem xét ví dụ: 1 2 3 4 5. Sắp xếp giảm: 5 4 3 2 1.
    // arr[0]=5. h=5. i=1. a[1]=4. h = min(4, 4) = 4.
    // i=2. a[2]=3. h = min(3, 3) = 3.
    // ...
    // i=5. Loop end. cout 5.
    // Logic này tìm số lượng viên gạch đầu tiên mà tại đó điều kiện bị vi phạm.

    // Để dễ hiểu nhất, ta nên giải thích theo thuật toán "Greedy counting" (Approach 2) 
    // hoặc "Binary Search" (Approach 1).
    // Approach 3 này có thể được giải thích là một biến thể của Greedy.
    // Sắp xếp giảm dần.
    // Một chồng gạch có k viên (từ đáy lên) cần:
    // a[0] >= k-1 (nếu dùng viên lớn nhất làm đáy)
    // a[1] >= k-2
    // ...
    // a[k-1] >= 0
    // Khi duyệt giảm dần, ta cần tìm k lớn nhất sao cho a[k-1] >= 0 (luôn đúng), a[k-2] >= 1...
    // Code mẫu đang làm: Giả sử ta có thể tạo độ cao a[0].
    // Sau đó thử giảm độ cao xuống.
    int height = a[0];
    for (int i = 1; i < n; ++i) {
        if (height == 0) break;
        // Viên gạch thứ i có thể nằm ở độ cao height-1 không?
        // Nếu height là độ cao tối đa có thể chịu bởi các viên trên,
        // thì a[i] >= height - 1 là điều kiện.
        // Code làm: height = min(height - 1, a[i]);
        // Nếu a[i] < height - 1, thì không thể đạt độ cao height nữa, phải giảm xuống a[i] + 1.
        // Nếu a[i] >= height - 1, thì độ cao giảm đi 1 đơn vị (vì đã dùng thêm 1 viên).
        height = min(height - 1, a[i]);
    }
    cout << a[0] - height << endl;
    // Wait, output của code mẫu là i. 
    // Vòng lặp i chạy từ 1 đến n.
    // Nếu height không bao giờ bằng 0, i sẽ là n.
    // Nếu height về 0 ở bước i, vòng lặp break, i không tăng nữa.
    // Vòng lặp dừng khi i = index của viên gạch cuối cùng dùng được + 1.
    // Do đó cout i là chính xác.
    // Tuy nhiên, có trường hợp a[0] < n.
    // Code mẫu in ra i.
    // Nếu a[0] < n, ví dụ a = [2, ...].
    // height=2. i=1. height=1. i=2. height=0 (nếu a[1] < 1). Break. i=2.
    // cout 2.
    // Đáp án đúng.
    // Vậy code mẫu thực ra là:
    sort(a.rbegin(), a.rend());
    int h = a[0];
    int i;
    for (i = 1; i < n; ++i) {
        if (h == 0) break;
        h = min(h - 1, a[i]);
    }
    cout << i;
  • Time Complexity: O(N log N)
  • Space Complexity: O(N)

Thuật toán này bắt đầu bằng cách sắp xếp các viên gạch theo độ cứng giảm dần. Nó giả định rằng độ cao tối đa có thể đạt được ít nhất là bằng độ cứng của viên gạch lớn nhất (a[0]). Biến h lưu trữ độ cao tối đa có thể duy trì được sau khi xét các viên gạch. Với mỗi viên gạch tiếp theo, nó kiểm tra xem viên gạch này có thể duy trì độ cao hiện tại không. Nếu a[i] >= h - 1, viên gạch này có thể nằm ở vị trí h-1 (từ trên xuống) trong khi vẫn giữ nguyên tổng độ cao. Tuy nhiên, vì ta đã dùng thêm một viên gạch, độ cao tối đa có thể giảm đi 1 (từ h xuống h-1). Nếu a[i] < h - 1, viên gạch này không chịu được tải trọng của các viên phía trên ở độ cao hiện tại, do đó độ cao phải giảm xuống a[i] + 1. Biến h được cập nhật bằng min(h - 1, a[i]). Vòng lặp dừng lại khi h về 0 hoặc hết gạch. Số lần lặp chính là độ cao tối đa.

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

Cách tiếp cận Time Space Tên
1 O(N log N) O(N) Sắp xếp và Thử nghiệm (Binary Search)
2 O(N log N) O(N) Sắp xếp và Duyệt tuyến tính (Greedy)
3 O(N log N) O(N) Sắp xếp Giảm dần và Xây dựng từ trên xuống

Bài học kinh nghiệm

  • Vấn đề có thể được quy về bài toán tìm số nguyên k lớn nhất sao cho tồn tại k phần tử trong mảng thỏa mãn một số điều kiện liên quan đến thứ tự và giá trị.
  • Sau khi sắp xếp mảng, ta có thể áp dụng các thuật toán tham lam (Greedy) hoặc tìm kiếm nhị phân (Binary Search) để giải quyết bài toán một cách hiệu quả.
  • Một quan sát quan trọng là nếu ta chọn k viên gạch để tạo thành chồng cao k, thì nên chọn k viên gạch có độ cứng lớn nhất, và sắp xếp chúng sao cho viên có độ cứng nhỏ nhất trong số đó ở vị trí đáy (nếu xét điều kiện tổng quát) hoặc áp dụng các điều kiện Greedy.

Lỗi thường gặp

  • Xử lý sai trường hợp khi độ cứng bằng 0 hoặc khi N rất nhỏ.
  • Lỗi truy cập ngoài mảng khi sử dụng các chỉ số phức tạp trong vòng lặp lồng nhau.
  • Độ phức tạp thuật toán không tốt (Ví dụ: Brute force O(N^2)) dẫn đến quá thời gian với N=100000.
  • Nhầm lẫn giữa số viên gạch có thể đặt lên trên và độ cao của chồng gạch.

Bình luận

Please read the guidelines before commenting.


Không có bình luận tại thời điểm này.