思路:找到第一个 1,将其之后连续的 0 最多的那个右端点与这个 1 的位置进行翻转。例:10001000100,连续 0 的最大值为 3,第一次出现的右端点下标为 7,故答案为:00010001100。
#include<bits/stdc++.h>
using namespace std;
#define int long long
char s[100000];
int ll=-1,rr=-1;
signed main(){
cin>>s;
for(int l=0;l<strlen(s);l++){
if(s[l]=='1'){
ll=l;
break;
}
}
int maxx=0,where=-1,now_ans=0,kk=-1;
for(int r=strlen(s)-1;r>=ll;r--){
if(s[r]=='1'){
if(now_ans>maxx){
maxx=now_ans;
where=kk;
}
now_ans=0;
kk=-1;
}
else if(s[r]=='0'){
if(kk==-1){
kk=r;
}
now_ans++;
}
}
if(now_ans>maxx){
maxx=now_ans;
where=kk;
}
rr=where;
if((ll==rr&&ll==-1)){
for(int i=0;i<strlen(s);i++){
cout<<s[i];
}
}
else{
for(int i=0;i<ll;i++){
cout<<s[i];
}
for(int i=rr;i>=ll;i--){
cout<<s[i];
}
for(int i=rr+1;i<strlen(s);i++){
cout<<s[i];
}
}
return 0;
}
//101001
//01111000
//00011010