Fun fact: Bài này lời giải tác giả là \(O(n)\) nhưng đa số các bạn đều làm \(O(n \log A)\).

Cách 1: (Lời giải của đa số các bạn)

Ý tưởng cho bài này là chặt nhị phân trên đáp số. Hay nói cách khác, ở đây chúng ta chặt nhị phân đại lượng thời gian. Câu hỏi đặt ra là: Giả sử các con kiến có không quá \(t\) giây, liệu chúng có thể tạo thành một hàng như nhà vua mong muốn hay không? (*)

Nhận xét rằng, nếu các con kiến có thể hoàn thành việc xếp hàng trong \(t\) giây, thì chắc chúng cũng có thể hoàn thành nếu có \(t + 1\) giây. Vì vậy đáp số sẽ là số \(t\) nhỏ nhất mà các con kiến có thể hoàn thành việc xếp hàng. Để tìm số \(t\) này các bạn có thể chặt nhị phân trên đoạn từ \(0\) đến \(10^9\) vì có thể thấy rằng với \(10^9\) giây, các con kiến có thể hoàn thành công việc.

Công việc cuối cùng còn lại là giải quyết câu hỏi (*). Việc này có thể được thực hiện một cách tham lam như sau:

• Ta thấy rằng, để tối ưu thì con kiến số \(1\) sẽ di chuyển sang trái \(t\) bước. Hay \(b_1 = a_1 - t\).
• Con kiến thứ hai sẽ di chuyển sang trái nhiều nhất có thể. Điều kiện là \(b_2 > b_1\) và \(a_2 - t \leq b_2 \leq a_2 + t\). Nếu \(a_2 + t < b_1\) thì không thể hoàn thành công việc. Ngược lại, ta chọn \(b_2 = max(b_1 + 1, a_2 - t)\).
• Con kiến thứ ba cũng làm tương tự con kiến thứ hai nhưng dựa vào \(b_2\) thay vì \(b_1\).
  ...

Công việc có thể hoàn thành nếu dãy \(b\) được hoàn thành từ \(1\) tới \(n\).

Độ phức tạp cho mỗi lần kiểm tra là \(O(n)\). Do đó độ phức tạp cuối cùng là \(O(n \log A)\) với \(A\) là kết quả lớn nhất có thể của đáp số. Ở đây, \(A = 10^9\).

Cách 2: (Lời giải của tác giả)

Đầu tiên, chúng ta sẽ tạo một dãy mới \(a[i] = a[i] - i\) và đưa bài toán về dựng dãy \(b\) không giảm thay vì tăng nghiêm ngặt. . Sau khi dựng được dãy \(b\) không giảm, ta sẽ in ra đáp số là dãy \(c\) mà \(c[i] = i + b[i]\). Chẳng hạn thay vì xét \(a = [3, 2, 1]\), chúng ta sẽ xét dãy \([2, 0, -2]\). Dãy \(b\) sẽ là \([0, 0, 0]\) và từ đó in ra \([1, 2, 3]\).

Đầu tiên, cần tìm 2 con kiến nghịch thế mà khoảng cách giữa chúng là lớn nhất. Nói cách khác, cần tìm \(i < j\) sao cho \(a[i] > a[j]\) và \(d = a[j] - a[i]\) lớn nhất. Khi đó thời gian cần dùng ít nhất là \(res = \left \lceil \dfrac{d}{2} \right \rceil\). Trường hợp tốt nhất là khi 2 con kiến đó đi ngược chiều rồi gặp nhau. Ví dụ con kiến ở \(0\) muốn xếp sau con ở \(5\) thì cần \(3\)s.

Ta sẽ dựng một dãy \(b\) để chứng minh đây là con số tối ưu. Có nhiều cách dựng, một trong số đó là áp dụng tư tưởng của bài trên. Một cách khác là dựng như sau: \(b[i] = max(a[1], a[2], ..., a[i]) - res\).

Chứng minh: Dãy \(b\) rõ ràng là một dãy không giảm. Do đó ta chỉ cần chứng minh \(|a[i] - b[i]| \leq res\).

Gọi \(a[j]\) là số hạng lớn nhất trong \(i\) số đầu tiên, \(b[i] = a[j] - res\). Ta cần chứng minh \(|a[i] - a[j] + res| \leq res\). Điều này đúng vì \(0 \leq a[j] - a[i] \leq d \leq 2 * res\).

Cách này cho chúng ta lời giải \(O(n)\)

Code tham khảo:

Cách 1: letangphuquy

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

typedef long long Int;
int n;
Int* a;
Int* b;
bool check(Int lim) {
    for (int i = 0; i < n; i++) {
        b[i] = a[i];
        if (!i) b[i] -= lim;        
        else {
            if (a[i] < b[i - 1])
                b[i] = min(b[i - 1] + 1, b[i] + lim);
            else if (b[i - 1] + 1 <= b[i] + lim)
                b[i] = max(b[i - 1] + 1, b[i] - lim);
            if (b[i - 1] >= b[i]) return false;
        }   
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    a = new Int[n];
    b = new Int[n];
    for (int i = 0; i < n; i++) cin >> a[i];

    Int lo = 0, hi = 1e18, ans = - 1;
    while (lo <= hi) {
        Int mi = lo + hi >> 1;
        if (!check(mi)) lo = mi + 1;
        else ans = mi, hi = mi - 1;
    }
    cout << ans << "\n";
    cerr << ans << "\n";
    check(ans);
    for (int i = 0; i < n; i++) cout << b[i] << " ";
//  for (int i = 0; i < n; i++) cerr << b[i] << " ";
}

Cách 2:

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

int a[300005], b[300005];

int main() {
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(NULL);

    int n;
    cin >> n;

    int maxVal = -1e9;
    int time = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] -= i;
        maxVal = max(maxVal, a[i]);
        b[i] = maxVal + i;

        time = max(time, (maxVal - a[i] + 1) / 2);
    }

    cout << time << '\n';
    for (int i = 1; i <= n; i++) {
        cout << b[i] - time << " ";
    }


    return 0;
}