Tutorial — Khôi Phục Dãy

Hãy xét số lượng số $0$ cần điền trong dãy $a$, chính là độ dài $k$ của dãy $b$. Điều gì sẽ xảy ra khi $k \ge 2$ so với khi $k = 1$?

Khi $k \ge 2$, tập hợp $b$ chứa ít nhất hai số phân biệt. Nếu có một cách xếp khiến dãy kết quả tăng nghiêm ngặt, việc đổi chỗ hai phần tử bất kỳ từ $b$ sẽ làm thay đổi thứ tự và phá vỡ tính tăng nghiêm ngặt đó.

Với $k > 1$, đáp án luôn là Yes. Với $k = 1$, hãy điền phần tử duy nhất của $b$ vào vị trí $0$ duy nhất trong $a$, sau đó kiểm tra xem dãy kết quả có tăng nghiêm ngặt hay không trong thời gian $O(n)$.