Tóm tắt đề bài

Cho một dãy số nguyên dương \(a_1, a_2, \dots, a_n\) biểu diễn chiều cao lớp kem tại các vị trí trên chiếc bánh. Khi quét dao ở độ cao \(h\), nếu kem ở vị trí \(i\) cao hơn \(h\) thì phần thừa sẽ bị đẩy sang vị trí \(i+1\).

Với mỗi tiền tố gồm \(i\) phần tử đầu tiên (\(1 \le i \le n\)), hãy tìm chiều cao lớn nhất có thể của lớp kem sau khi làm phẳng sao cho tất cả \(i\) vị trí này có chiều cao bằng nhau.

Phân tích

• Điều kiện giới hạn: Số lượng truy vấn \(t \le 10^4\), kích thước mảng \(n \le 2 \times 10^5\), tổng của \(n\) qua các truy vấn không quá lớn, giá trị các phần tử \(a_i \le 10^9\).
• Nhận xét quan trọng:
  • Khi xét đoạn từ \(1\) đến \(i\), tổng lượng kem bảo toàn qua các lần đẩy (trừ phần kem bị đẩy ra khỏi vị trí \(i\)). Tuy nhiên, vì chúng ta muốn tất cả \(i\) vị trí đều có chiều cao bằng nhau (gọi là \(H\)), và toàn bộ phần kem thừa từ các vị trí cao hơn sẽ dồn vào các vị trí thấp hơn, tổng lượng kem từ vị trí \(1\) đến \(i\) sẽ được phân phối đều cho \(i\) phần tử.
  • Lượng kem tổng cộng của \(i\) phần tử đầu tiên là \(\sum_{j=1}^{i} a_j\).
  • Khi san phẳng thành \(i\) phần bằng nhau, chiều cao tối đa lý thuyết cho mỗi phần là phần nguyên của trung bình cộng: \(\lfloor \frac{\sum_{j=1}^{i} a_j}{i} \rfloor\).
  • Liệu chiều cao này có luôn đạt được bằng cách chọn một độ cao dao phù hợp không? Theo tính chất của thao tác đẩy kem từ trái sang phải, ta luôn có thể chọn chiều cao dao sao cho kết quả san phẳng cho ra giá trị lớn nhất có thể không vượt quá giới hạn vật lý này, và giá trị tối ưu chính là \(\lfloor \frac{\sum_{j=1}^{i} a_j}{i} \rfloor\).

Cách làm đơn giản (Brute Force)

Ý tưởng

Với mỗi tiền tố từ \(1\) đến \(i\), ta có thể thử tất cả các chiều cao dao \(h\) có thể hoặc mô phỏng lại quá trình đẩy kem từ trái sang phải để tìm chiều cao san phẳng lớn nhất đạt được tất cả các phần tử bằng nhau.

Độ phức tạp

• Thời gian: \(O(n^2)\) hoặc \(O(n^3)\) tùy cách mô phỏng.
• Đánh giá: Quá chậm và sẽ bị quá thời gian (Time Limit Exceeded) với \(n \le 2 \times 10^5\).

Code Brute Force

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];

        for (int i = 0; i < n; i++) {
            long long sum = 0;
            for (int j = 0; j <= i; j++) sum += a[j];
            cout << sum / (i + 1) << " ";
        }
        cout << "\n";
    }
}

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    t = int(input_data[0])
    idx = 1
    for _ in range(t):
        n = int(input_data[idx])
        idx += 1
        a = []
        for _ in range(n):
            a.append(int(input_data[idx]))
            idx += 1

        current_sum = 0
        ans = []
        for i in range(n):
            current_sum += a[i]
            ans.append(current_sum // (i + 1))
        print(*(ans))

solve()

(Lưu ý: Đoạn code brute force trên thực chất đã vô tình đạt độ phức tạp \(O(n)\) ở bản cài đặt này, nhưng bản chất tư duy vét cạn qua việc thử từng độ cao dao sẽ là \(O(n^2)\)).

Hướng giải quyết (Tối ưu)

Nhận xét

• Nhờ việc bảo toàn tổng lượng kem qua các vị trí, chiều cao đều nhau lớn nhất cho \(i\) phần tử đầu tiên chính là trung bình cộng của \(i\) phần tử đó.
• Ta chỉ cần duy trì tổng tiền tố (sum) từ phần tử đầu tiên đến phần tử thứ \(i\), sau đó tính giá trị sum / (i + 1).
• Để các kết quả không bị giảm đột ngột (vì đôi khi chiều cao san phẳng bị giới hạn bởi các phần tử phía trước), kết quả tại mỗi bước \(i\) thực chất là \(\min\) của các trung bình cộng từ đầu đến vị trí hiện tại.

Thuật toán

1. Khởi tạo biến sum = 0 và biến ans = 1e18 (hoặc giá trị vô cực).
2. Duyệt qua từng phần tử \(i\) từ \(0\) đến \(n-1\):
   • Cộng \(a_i\) vào sum.
   • Cập nhật chiều cao tốt nhất có thể đạt được: ans = min(ans, sum / (i + 1)).
   • In ra giá trị ans tại bước hiện tại.

Độ phức tạp

• Thời gian: \(O(n)\) cho mỗi truy vấn, tổng thời gian là \(O(\sum n)\), hoàn toàn chạy nhanh trong giới hạn cho phép.
• Bộ nhớ: \(O(n)\) để lưu mảng đầu vào.

Code tham khảo

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;

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

    long long ans = 2e18; // Khởi tạo giá trị vô cùng lớn
    long long sum = 0;

    for (int i = 0; i < n; i++) {
        sum += a[i];
        // Tính trung bình cộng của lượng kem từ đầu đến vị trí hiện tại
        ans = min(ans, sum / (i + 1));
        cout << ans << " ";
    }
    cout << "\n";
}

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

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    t = int(input_data[0])
    idx = 1
    out = []
    for _ in range(t):
        n = int(input_data[idx])
        idx += 1
        ans = 2 * 10**18
        total_sum = 0
        current_ans = []
        for i in range(n):
            val = int(input_data[idx])
            idx += 1
            total_sum += val
            current_val = total_sum // (i + 1)
            if current_val < ans:
                ans = current_val
            current_ans.append(str(ans))
        out.append(" ".join(current_ans))
    print("\n".join(out))

if __name__ == '__main__':
    solve()