1串

题目大意

给定一个只包含01的序列，可以执行以下操作

1. 选择一个1
2. 将其移动到左边最近的0所在位置，原先位置被0填充

询问，最起码需要几次操作才可以让所有的1贴在一起。

思路解析

我们可以想到，如果想要将所有的1连在一起，那么我们则需要将在序列当中出现的第一个1与最后一个1的中间所有0都给他排除掉，才可以完成。可以将每一次操作视为是·删除·首1与尾1之间的1个0，那么最终执行的次数则为首1与尾1之间0的个数。

例如: 10001 最少操作次数3，因为首个1与尾巴的1之间存在3个空格，101010101为4，理由如上。

时间复杂度

$O(n)$

代码演示

/*
    Yuilice今天睡饱了吗？
*/
#include<bits/stdc++.h>
using namespace std;

int a[55];  // 定义一个大小为55的数组

int main() {
    int n;  // 读取测试用例中的数目
    cin >> n;
    int count = 0;
    int left = 0;
    
    // 读取输入并找出第一个非0的位置
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        if(!left && a[i]) left = i;  // 找到第一个非0元素的位置
    }
    
    // 找出最后一个非0的位置
    int right = 0;
    for(int i = n; i >= 1; i--) {
        if(!right && a[i]) {
            right = i;
            break;
        }
    }
    
    // 统计left和right之间的0的个数
    for(int i = left; i <= right; i++) {
        if(!a[i]) count++;
    }
    
    cout << count << endl;  // 输出结果
    
    return 0;
}