Tóm tắt đề bài

Có \(n\) bàn thi đấu xếp hàng ngang, bàn thứ \(i\) có \(a_i\) khối Rubik. Có \(m\) tuyển thủ xuất phát từ bàn 1 tại giây thứ 0. Mỗi giây, một tuyển thủ có thể:

1. Di chuyển sang bàn kế tiếp (\(i \to i+1\)).
2. Giải xong 1 khối Rubik tại bàn hiện tại.

Tìm thời gian tối thiểu \(t\) để giải hết toàn bộ Rubik ở tất cả các bàn.

Phân tích

• Điều kiện: \(n, m \le 10^5\), \(a_i \le 10^9\). Tổng số Rubik có thể rất lớn, lên tới \(10^{14}\).
• Nhận xét quan trọng:
  • Nếu với thời gian \(T\) ta có thể giải hết Rubik, thì với thời gian \(T+1\) ta cũng chắc chắn giải hết được. Đây là tính chất đơn điệu, cho phép ta sử dụng Tìm kiếm nhị phân trên kết quả.
  • Để giải quyết bài toán trong thời gian \(T\), mỗi tuyển thủ sẽ mất một khoảng thời gian để di chuyển đến bàn xa nhất mà họ cần làm việc. Nếu một tuyển thủ đi đến bàn \(k\), họ mất \(k\) giây để di chuyển (từ vị trí xuất phát đến bàn 1 mất 1 giây, đến bàn \(k\) mất \(k\) giây), vậy họ còn \(T - k\) giây để giải Rubik.
  • Chiến thuật tối ưu là ưu tiên giải các khối Rubik ở các bàn xa nhất trước. Vì các bàn ở xa tốn nhiều thời gian di chuyển nhất, ta nên dồn lực giải quyết chúng để giảm bớt gánh nặng cho các tuyển thủ khác.

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

Với các subtask nhỏ, ta có thể mô phỏng quá trình theo từng giây hoặc thử mọi thời gian \(T\) từ nhỏ đến lớn. Tuy nhiên, do \(a_i\) và \(T\) có thể rất lớn, cách này không khả thi. Một cách tiếp cận "tham lam" đơn giản là cho từng người một đi từ bàn \(n\) ngược về bàn 1 và giải nhiều nhất có thể trong thời gian \(T\).

Độ phức tạp

• Thời gian: \(O(T \cdot m)\) hoặc \(O(\sum a_i)\), quá chậm với \(n, m = 10^5\).

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

1. Tìm kiếm nhị phân

Ta tìm kiếm nhị phân giá trị thời gian \(T\) trong khoảng từ \(1\) đến \(10^{15}\) (một giá trị đủ lớn để bao quát trường hợp xấu nhất).

2. Hàm kiểm tra check(T)

Để kiểm tra xem với thời gian \(T\) có thể giải hết Rubik hay không:

1. Sao chép mảng \(a\) sang một mảng tạm \(c\) để không làm thay đổi dữ liệu gốc.
2. Xác định vị trí bàn xa nhất còn Rubik (gọi là id).
3. Duyệt qua từng tuyển thủ từ \(1\) đến \(m\):
   • Tìm bàn xa nhất hiện tại có Rubik (id). Nếu id < 1, nghĩa là đã giải xong hết, trả về true.
   • Tuyển thủ này sẽ đi đến bàn id. Thời gian còn lại để giải Rubik là \(rem = T - id\).
   • Nếu \(rem > 0\), tuyển thủ này sẽ giải Rubik tại bàn id, sau đó nếu vẫn còn thời gian, họ sẽ lùi dần về các bàn \(id-1, id-2, \dots\) để giải tiếp cho đến khi hết thời gian \(rem\) hoặc hết Rubik.
4. Sau khi \(m\) tuyển thủ đã làm việc, nếu vẫn còn bàn nào có Rubik (id >= 1), trả về false. Ngược lại trả về true.

Ví dụ minh họa

Với \(n=5, m=3\) và \(a = [0, 3, 2, 1, 8]\), thử \(T=10\):

• Tuyển thủ 1: Đến bàn 5 (mất 5s), còn 5s giải được 5 khối ở bàn 5. Bàn 5 còn 3 khối.
• Tuyển thủ 2: Đến bàn 5 (mất 5s), còn 5s giải nốt 3 khối ở bàn 5 và 1 khối ở bàn 4, 1 khối ở bàn 3. Bàn 3 còn 1 khối.
• Tuyển thủ 3: Đến bàn 3 (mất 3s), còn 7s giải nốt 1 khối ở bàn 3 và 3 khối ở bàn 2. Hết Rubik!
• Kết quả: \(T=10\) thỏa mãn.

Độ phức tạp

• Thời gian: \(O(\log(10^{15}) \cdot (n + m))\). Với mỗi bước nhị phân, ta chỉ duyệt qua \(m\) tuyển thủ và con trỏ id chỉ chạy ngược từ \(n\) về \(1\) một lần duy nhất.
• Bộ nhớ: \(O(n)\) để lưu trữ mảng số lượng Rubik.

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<long long> a;

bool check(long long T) {
    vector<long long> c = a;
    int id = n;

    // Duyệt qua từng tuyển thủ
    for (int i = 1; i <= m; i++) {
        // Tìm bàn xa nhất còn Rubik
        while (id >= 1 && c[id] <= 0) id--;
        if (id < 1) return true;

        // Thời gian còn lại sau khi di chuyển đến bàn id
        long long rem = T - id;
        if (rem <= 0) continue;

        // Giải Rubik tại bàn id và các bàn trước đó
        while (id >= 1 && rem > 0) {
            if (rem >= c[id]) {
                rem -= c[id];
                c[id] = 0;
                while (id >= 1 && c[id] <= 0) id--;
            } else {
                c[id] -= rem;
                rem = 0;
            }
        }
        if (id < 1) return true;
    }

    while (id >= 1 && c[id] <= 0) id--;
    return id < 1;
}

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

    if (cin >> n >> m) {
        a.resize(n + 1);
        for (int i = 1; i <= n; i++) cin >> a[i];

        long long low = 1, high = 1e15; // 1e15 là đủ lớn cho n=1e5, a_i=1e9
        long long ans = high;

        while (low <= high) {
            long long mid = low + (high - low) / 2;
            if (check(mid)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

import sys

def solve():
    # Đọc n và m
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    n = int(input_data[0])
    m = int(input_data[1])
    a = [0] + [int(x) for x in input_data[2:]]

    def check(T):
        c = list(a)
        current_id = n

        for _ in range(m):
            # Tìm bàn xa nhất còn Rubik
            while current_id >= 1 and c[current_id] <= 0:
                current_id -= 1

            if current_id < 1:
                return True

            rem = T - current_id
            if rem <= 0:
                continue

            # Giải Rubik từ bàn current_id trở về trước
            while current_id >= 1 and rem > 0:
                if rem >= c[current_id]:
                    rem -= c[current_id]
                    c[current_id] = 0
                    while current_id >= 1 and c[current_id] <= 0:
                        current_id -= 1
                else:
                    c[current_id] -= rem
                    rem = 0

            if current_id < 1:
                return True

        return False

    low = 1
    high = 10**15
    ans = high

    while low <= high:
        mid = (low + high) // 2
        if check(mid):
            ans = mid
            high = mid - 1
        else:
            low = mid + 1

    print(ans)

if __name__ == "__main__":
    solve()