首页 > 其他分享 >edu145-D

edu145-D

时间:2023-04-14 12:13:55浏览次数:60  
标签:const 分界线 int edu145 long solve

题目链接:https://codeforces.com/problemset/problem/1809/D

一个关键的地方没想到,没有想到枚举分界线。

思路:最终改成的字符串的样子一定是这样的:以某个点为分界线,左边全是0,右边全是1。所以可以枚举分界线(分界线的值为1,左边去掉为1的,右边去掉为0的),当且仅当\(s_i=0,s_{i-1}=1\)交换比删除更优,特判一下即可。

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
const long long val = 1e12;
int pre1[N],pre0[N];
void solve(){
    string s;
    cin>>s;
    int n = s.length();
    s = ' '+s;
    for (int i=1;i<=n;i++){
        pre1[i] = pre1[i-1];
        pre0[i] = pre0[i-1];
        if (s[i]=='1') pre1[i]++;
        else pre0[i]++;
    }
    long long ans = 1e18;
    for (int i=1;i<=n+1;i++){
        long long temp = 0;
        temp += (pre0[n]-pre0[i-1])*(val+1);
        temp += (pre1[i-1]-pre1[0])*(val+1);
        if (s[i]=='0'&&s[i-1]=='1'){
            temp -= 2*(val+1);
            temp += val;
        }
        ans = min(ans,temp);
    }
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    T = 1;
    cin>>T;
    while(T--) solve();
    return 0;
}

标签:const,分界线,int,edu145,long,solve
From: https://www.cnblogs.com/xjwrr/p/17317897.html

相关文章