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.

Author: bedao

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

Please read the guidelines before commenting.


There are no comments at the moment.