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

bravo11111111 · 2025-01-12 12:01:12 · 题解

分析如下

这道题就是一道贪心，首先有 n 全灭盏灯，要用最少的操作使灯满足要求。因为第一次操作不需要代价且可以一次性调整从第 1 到第 i 盏灯。所以第一次操作我们要使让不满足要求的灯尽可能少。然后再加上不满足灯的个数就行了。

AC代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000000],ans,b[500001],k,sum,cnt;
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];
        if(a[i])cnt++;//统计不满组要求的灯
    }
    k=cnt;//不进行第一次操作的代价
    for(int i=1; i<=n; i++) {
        b[i]=b[i-1];
        if(a[i]==0)b[i]++;//开了不该开的灯
        else cnt--;//
        if(k>b[i]+cnt) {
            k=b[i]+cnt;//统计答案
        }
    }
    cout<<k;
    return 0;
}