Biến đổi dãy nhị phân

Tác giả:

cuom1999

Dạng bài

Điểm: 200 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số \(a_1, a_2, ..., a_n\), trong đó \(a_i = 0\) hoặc \(1\). Mỗi thao tác, bạn được chọn hai số kề nhau và hoán đổi chúng. Hãy tìm số thao tác ít nhất để sắp xếp dãy \(a\) tăng dần.

Ví dụ, \(a = [1, 0, 0]\). Chúng ta cần 2 thao tác.

Thao tác 1: Hoán đổi \(a_1\) và \(a_2\). \(a = [0, 1, 0]\).
Thao tác 2: Hoán đổi \(a_2\) và \(a_3\). \(a = [0, 0, 1]\). Lúc này dãy \(a\) đã được sắp xếp tăng dần.

Input

Dòng đầu chứa một số tự nhiên \(n\), độ dài của dãy. \((1 \leq n \leq 5 * 10^5)\)
Dòng thứ hai chứa \(n\) số tự nhiên \(a_1, a_2, ..., a_n \ (0 \leq a_i \leq 1)\)

Output

In ra một số tự nhiên là số thao tác ít nhất cần sử dụng

Scoring

Subtask \(1\) (\(30\%\) số điểm): \(n \leq 10\)
Subtask \(2\) (\(30\%\) số điểm): \(n \leq 1000\)
Subtask \(3\) (\(40\%\) số điểm): \(n \leq 5 * 10^5\)

Example

Test 1

Input

3
1 0 0

Output

Test 2

Input

4
0 0 1 1

Output

Bình luận

1 cách làm khác :
Tưởng tượng khi dãy đã hoàn thành, vì dãy là nhị phân nên tất cả số 1 đều sẽ dồn về cuối dãy
-> Duyệt ngược từ cuối dãy về, nếu số \(Ai\) hiện đang xét là 1 thì tính số lần cần đổi để cho số 1 đấy về cuối dãy (tức đưa vị trí x cuối cùng của dãy mà \(Ax\) = 0 )
Code AC:

Thử imple trước đi!!!

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define __Habaxl__ signed main()
#define ll long long
#define ull unsigned long long
#define pb push_back
#define fir first
#define sec second
#define MOD 1000000007
#define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
#define ALL(x) (x).begin(),(x).end()
#define TIME (1.0*clock()/CLOCKS_PER_SEC)
using namespace std;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
ll i,n,a[500005],tmp,res=0;
void solve(){
cin >> n;
for (i=1;i<=n;i++)
    cin >> a[i];
tmp=n;
while (a[tmp]==1)
    tmp--;
for (i=tmp;i>=1;i--)
    if (a[i]==1){
        res+=tmp-i;
        tmp--;
    }
cout << res;
}
__Habaxl__{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
freopen("test1");
ll q=1;
//cin >> q;
while (q--){
    solve();
}
cerr << '\n' << "Time elapsed " << TIME << "s.\n";
return (0);
}

//trong cac loai cay tao,cay xoai,cay cam, cay ma em thich nhat la cay phan doan