ACM 训练日志记录 · 思考 · 成长
提交 / 修改记录
王梓豪 / 题目列表训练档案
导出

D. Falling Concrete

来源：Codeforces ★ 1300

本题活力0.64按难度、完成结果与训练证据估算

算法如山行则将至

王梓豪 的主页

题目描述

C. AND, OR, Sort!
time limit per test2 seconds
memory limit per test256 megabytes
You are given a binary string∗
s
of length n
.

You may perform the following operation any number of times (possibly zero):

choose an integer i
(1≤i≤n
), and replace si
with either the bitwise AND or the bitwise OR of s1,s2,…,si
.
Note that the bitwise AND or bitwise OR of a single element is equal to the element itself.

Your goal is to make s
sorted in non-decreasing order†
.

Find the minimum number of operations required to sort s
in non-decreasing order.

∗
A binary string only contains characters 0
and 1
.

†
If s
is in non-decreasing order, then s1≤s2≤…≤sn
.

Input
The first line contains a single integer t
(1≤t≤104
) — the number of test cases.

The first line of each test case contains a single integer n
(2≤n≤2⋅105
) — the length of the binary string s
.

The second line of each test case contains the binary string s
of length n
. Each character of s
is either 0 or 1.

It is guaranteed that the sum of n
over all test cases does not exceed 2⋅105
.

Output
For each test case, print a single integer — the minimum number of operations required to sort s
in non-decreasing order.

Example
InputCopy
6
4
0011
4
1000
5
01000
8
01001101
7
0101010
7
0111101
OutputCopy
0
3
1
2
3
1
Note
In the first test case, the string is already sorted, so no operations are required.

In the second test case, we can use bitwise OR to change the last three characters to 1, obtaining 1111 in 3
operations.

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--) {
        int n;
        string s;
        cin>>n>>s;
        
        int cnt1=0, cnt0=0;
        int flag=-1;
        
    for(int i=0; i<s.size(); i++) {
            if(s[i]=='0') cnt0++;
            else cnt1++;
            if(flag==-1 && s[i]=='1') flag=i;
        }
        
        if(s[0]=='1') {
            cout<<cnt0<<endl;
            continue;
        }
        
        vector<int> a(n+1, 0);
        for(int i=0; i<n; i++) {
            if(s[i]=='1') a[i+1] = a[i] + 1;
            else a[i+1] = a[i];
        }
        
        int min_ = INT_MAX;
        
        for(int i=0; i<=n; i++) {
            int l1 = a[i];
            int r0 = (n-i) - (a[n]-a[i]);
            int ops = l1 + r0;
            if(flag==-1 && i<n) {
                continue;
            }
            if(flag!=-1 && i>flag && r0>0) {
                if(a[n]-a[i] == 0) {
                    continue;
                }
            }
            min_ = min(min_, ops);
        }
        cout<<min_<<endl;
    }
    return 0;
}