Editorial for Bedao Mini Contest 08 - CHECKARRAY
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Giả sử ~a[i] \ge a[j]~. Ta có ~a[i] - a[j] \le 1~.
Có ~a[i] - a[j] = 0~, dễ thấy điều kiện này chỉ thỏa mãn khi ~a[i] = a[j]~. Vì vậy ta có thể chọn mọi cặp ~(i, j)~ với ~a[i] = a[j]~ và loại bỏ ~a[j]~. Sau đó, ta thu được một dãy các số phân biệt đôi một.
Có ~a[i] - a[j] = 1~, dễ thấy nếu sắp xếp lại dãy thu được trên, để thu dược dãy này về ~1~ phần tử, dãy đó phải tăng dần với hiệu hai số liên tiếp bằng ~1~. Ta thu dãy về ~1~ phần tử bằng cách chọn liên tiếp hai số bé nhất và loại bỏ số bé hơn.
Comments