题目链接: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