CF1913B 题解

luouhgy · 2024-01-05 20:51:45 · 题解

题目大意

一个 01 字符串 s，可以交换任意两个位置的元素，代价为 0；或删除一个元素，代价为 1。使得进行交换或删除后的字符串的每个 t_i 和 s_i 都不同，最少要用多少代价。

题目其实问我们把一个字符串 s 中的所有 1 都改为 0，把所有 0 都给成 1，一共需要操作几次。

思路

有点贪心的意思。

因为交换两个元素不仅一次可以满足两个元素，代价还为 0，所以我们要尽可能多交换两个元素，剩下的再删除。

操作 1 用的次数最多为字符串中 1 的个数，也就是将字符串中所有的 1 都删除；操作 0 用的次数最多为字符串中 0 的个数，也就是将字符串中所有的 0 删除。每发现一个可以交换的 1 或者是 0，就将操作 1 用的次数或操作 0 用的次数减少 1。

Code

#include<bits/stdc++.h>//万能头文件
using namespace std;
int t;
int cnt1;//字符串中操作1的次数
int cnt0;//字符串中操作0的次数
string s;
int main(){
    cin>>t;
    while(t--){
        cnt1=0,cnt0=0;//初始化
        cin>>s;
        int len=s.size();
        for(int i=0;i<len;i++){
            if(s[i]=='0')cnt1++;//字符串中0的个数
            else cnt0++;//字符串中1的个数
        }
        for(int i=0;i<len;i++){
            if(s[i]=='0'){
                if(cnt0)//可以交换一个0
                    cnt0--;//字符串中操作0的次数-1
                else//0已经交换完了
                    break;
            }else{
                if(cnt1)//可以交换一个1
                    cnt1--;//字符串中操作1的次数-1
                else//1已经交换完了
                    break;
            }
        }
        cout<<cnt1+cnt0<<endl;//字符串中操作1的次数+字符串中操作0的次数
    }
    return 0;//完工
}