题解：AT_icpc2015summer_day3_b Bits Are Dangerous

· · 题解

前置

题目链接

AC 记录

思路

因为每一次异或 1 只能改变最后一位，所以我们可以直接循环枚举，同时枚举循环左移和循环右移，最后输出最小值。

代码

#include<bits/stdc++.h>
using namespace std;
int cnt=0,sum=10000005;
int n;
int main(){
    string s;
    cin>>s;//输入
    n=s.size();
    for(int i=0;i<s.size();i++){
        if(s[i]=='1') cnt++;//看一看一共有多少个1
    }
    int i=1,j=n;
    string g=s+s;
    //为了方便枚举，可以将序列复制一次，这样就做到了"循环"
    for(int t=0;t<=cnt;t++){
        //因为最大的左移或右移次数取决于两个1之间的最大长度所以枚举cnt次
        while(g[i]=='0') i++;//左移
        while(t!=0&&g[j]=='0') j++;//右移
        int a=max(0,n-i);//保存
        int b=j-n;
        sum=min(sum,min(a,b)+a+b);//取最小
        i++,j++;
    }
    cout<<cnt*4+sum*7;
    //输出，因为有cnt个1，所以乘4，距离为sum，所以乘7
    return 0;
}