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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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(); }
Comments