原题链接

移动序列

给01串（其中必然有1），只能按照以下的规则移动：

image-20210617140139500求如何通过最小的次数让所有的1聚在一起。

思路

没有想明白，写了一个bfs搜索，毫不意外地tle了。

看了题解之后恍然大悟。注意到，从起始串到最后的目标串，区别在于中间的0全部被消除了，换而言之，最优的方案实际上就是逐个填充0，只要计算出两个1之间间隔的0个数。

实现

不需要考虑只有一个1的corner case，我们每次遍历的时候从1开始，遍历到下一个1开始，中间的长度就是0的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

const int N = 51;
int a[N];


int main(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        for(int i= 0;i<n;i++){
            cin>>a[i];
        }
        
        int zero_count = 0;
        for(int i = 0;i<n;){
            if(a[i] == 1){
                while(i<n && a[i] == 1)i++;
                int begin = i;
                while(i<n && a[i]==0)i++;
                int end = i;
                if(end < n)zero_count += end-begin;
            }else{
                i++;
            }
        }
        
        cout<<zero_count<<endl;
    }
    
    return 0;
}