Hướng dẫn giải của Bedao Mini Contest 16 - BINARY SORT


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: 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}~

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define int long long 
#define fo(i, a, b) for(int i = a; i <= b; i++)
#define _fo(i, a, b) for(int i = a; i >= b; i--)
#define foa(i, a) for (auto &i : a)
#define sz(a) ((int) a.size())
#define all(a) begin(a), end(a)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mk(x, y) make_pair(x, y)

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int LOG = 21; 
const int MASK = (1<<17)+5;
const int MAX = 1e6+5;
const int MOD = 998244353;
const int SQRT = 316;
const ll INF = 2e9;
const ll lon = 1e18;

int n;
int a[MAX];

ll solve() {
    ll res = 0, pos = 0;
    fo(i, 1, n) {
        if(a[i] == 1) continue;
        pos++;
        res += i-pos;
    }
    return res;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    cin >> n;
    fo(i, 1, n) cin >> a[i];
    cout << solve();
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.