题解：AT_joig2021_c イルミネーション 2 (Illumination 2)

题目传送门

题目大意

有两个序列 a 和 b，长度都为 n，a 的值都为 0。输入序列 b 后，你需要用若干次操作将 a 全变为 b。

两个操作：

• 花费 1 的单位时间，将此数取反。

• 花费 0 的单位时间，将此数前所有数（包括此数）全部取反（此操作只能最多使用一次）。

最后输出花费的最小时间。

取反：如果 i=1，则 i 取反后为 0。如果 i=0，则 i 取反后为 1。

思路

我们可以把题目最后一句话：

你需要用若干次操作将 a 全变为 b。

理解成：

你需要用若干次操作将 b 全部变为 0。

看到操作 2，只能使用最多一次，所以便可枚举操作 2 在哪里使用。

设编号为 i 的数的前面（包括它）有 s_{i} 个数为 1。

如果在 i 处使用，那么他前面 s_{i} 个数会变成 0，i-s_{i} 个数会变成 1。这些变为 1 的数要让他重新变为 0，需要花费 i-s_{i} 的时间。

之后我们还要让剩下的（i 之后的数） 1 全部变为 0，这些数一共有 s_{n}-s_{i} 个，让这些数变为 1 需要花费 s_{n}-s_{i} 的时间。

所以总结：我们假设在 i 这处使用操作 2，那么我们将所有数全部化为 0 的时间是 i-s_{i}+s_{n}-s_{i}。

最后将所有花费的时间取一个最小值就是答案了。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[200005],s[200005],ans=1e9,sum=0;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];
    for(int i=0;i<=n;i++){
        ans=min(ans,i-s[i]+s[n]-s[i]);
    }
    cout<<ans;
    return 0;
}