Editorial for Bedao Mini Contest 16 - BINARY SORT


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

Nhận xét: Số lần swap của thuật toán bằng với số lần swap khi ta thực hiện thuật toán sau:

for i = n - 2 to 0:
    for j = i + 1 to n - 1:
        if a[j] < a[j - 1]:
            swap(a[j], a[j - 1])

Với thuật toán trên, khi xét đến một ~a_i~ nào đó thì dãy ~a_{i+1},a_{i+2},\dots, a_{n-1}~ đã được sắp xếp. Khi đó số lần swap để ~a_i~ về đúng vị trí là: ~0~ nếu ~a_i=0~ và bằng số lượng số ~a_j=0~ với ~j=i+1\dots n-1~ nếu ~a_i=1~.

Như vậy, gọi ~cnt_i~ là số lượng ~a_j=0~ với ~j=i+1\dots n-1~ thì đáp án của bài toán sẽ là ~\sum_{i=0}^{n-2} a_i\times cnt_{i+1}~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.