题面描述

给定长度为$N$的数组 pvs，其中$pvs[i]=1$ 表示位置$i$ 有光伏板，$pvs[i]=0$ 表示位置$i$为空。现在可以在空位上安装“光伏优化器”，只要一个光伏板的左边或者右边有优化器，该光伏板就能提升发电效率。请计算最少需要安装多少个优化器，才能使所有光伏板都能被提升；如果无法覆盖所有光伏板，则返回$-1$。

思路

1. 贪心策略：从左到右遍历。

2. 遇到一个光伏板（即$pvs[i]=1$）且尚未被覆盖时，需要在它的邻位安装优化器。

3. 优先尝试向右安装：

   • 如果$i+1<N$ 且$pvs[i+1]=0$，就在位置$i+1$ 安装，并标记它能覆盖$i$以及未来可能的覆盖。
   • 否则再尝试向左：如果$i-1\ge0$ 且$pvs[i-1]=0$ 且该位置还未安装过优化器，就在位置$i-1$安装。

4. 若左右都无法安装，则无解，返回$-1$。

5. 记录已安装优化器的集合 opt，以及被覆盖（即相邻有优化器）的光伏板标记数组 covered，最终统计 opt 大小。

此策略保证：

• “向右优先”能最大范围地往后覆盖，减少未来安装需求，达到最少安装数。
• 单次遍历即可完成，时间复杂度$O(N)$，空间复杂度$O(N)$。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> pvs(N);
    for (int i = 0; i < N; i++) {
        cin >> pvs[i];
    }

    vector<bool> covered(N, false);  // 标记光伏板是否已被覆盖
    vector<bool> hasOpt(N, false);   // 标记位置是否安装了优化器
    int ans = 0;

    for (int i = 0; i < N; i++) {
        if (pvs[i] == 1 && !covered[i]) {
            // 优先尝试向右安装优化器
            if (i + 1 < N && pvs[i+1] == 0 && !hasOpt[i+1]) {
                hasOpt[i+1] = true;
                ans++;
                // 安装后，覆盖左右的光伏板
                if (i >= 0 && pvs[i] == 1) covered[i] = true;
                if (i+2 < N && pvs[i+2] == 1) covered[i+2] = true;
            }
            // 右侧不行，尝试左侧
            else if (i - 1 >= 0 && pvs[i-1] == 0 && !hasOpt[i-1]) {
                hasOpt[i-1] = true;
                ans++;
                if (i-2 >= 0 && pvs[i-2] == 1) covered[i-2] = true;
                if (i < N && pvs[i] == 1) covered[i] = true;
            }
            else {
                // 无法安装覆盖此光伏板
                cout << -1;
                return 0;
            }
        }
    }

    cout << ans;
    return 0;
}

Python

def min_optimizers(pvs):
    n = len(pvs)
    covered = [False] * n    # 标记是否被覆盖
    has_opt = [False] * n    # 标记是否安装优化器
    ans = 0

    for i in range(n):
        if pvs[i] == 1 and not covered[i]:
            # 优先向右安装
            if i + 1 < n and pvs[i+1] == 0 and not has_opt[i+1]:
                has_opt[i+1] = True
                ans += 1
                covered[i] = True
                if i + 2 < n and pvs[i+2] == 1:
                    covered[i+2] = True
            # 向右不行，尝试左侧
            elif i - 1 >= 0 and pvs[i-1] == 0 and not has_opt[i-1]:
                has_opt[i-1] = True
                ans += 1
                covered[i] = True
                if i - 2 >= 0 and pvs[i-2] == 1:
                    covered[i-2] = True
            else:
                return -1
    return ans

# 读入输出部分
if __name__ == "__main__":
    N = int(input().strip())
    pvs = list(map(int, input().split()))
    print(min_optimizers(pvs))

Java

import java.util.*;

public class Main {
    public static int minOptimizers(int[] pvs) {
        int n = pvs.length;
        boolean[] covered = new boolean[n];  // 标记是否被覆盖
        boolean[] hasOpt = new boolean[n];   // 标记是否安装优化器
        int ans = 0;

        for (int i = 0; i < n; i++) {
            if (pvs[i] == 1 && !covered[i]) {
                // 优先尝试向右安装
                if (i + 1 < n && pvs[i+1] == 0 && !hasOpt[i+1]) {
                    hasOpt[i+1] = true;
                    ans++;
                    covered[i] = true;
                    if (i + 2 < n && pvs[i+2] == 1) {
                        covered[i+2] = true;
                    }
                }
                // 向右不行，尝试左侧
                else if (i - 1 >= 0 && pvs[i-1] == 0 && !hasOpt[i-1]) {
                    hasOpt[i-1] = true;
                    ans++;
                    covered[i] = true;
                    if (i - 2 >= 0 && pvs[i-2] == 1) {
                        covered[i-2] = true;
                    }
                }
                else {
                    return -1;
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] pvs = new int[N];
        for (int i = 0; i < N; i++) {
            pvs[i] = sc.nextInt();
        }
        System.out.println(minOptimizers(pvs));
    }
}

题目内容

光伏优化器可以用来提升光伏板的发电效率，现在需要给一排已经安装好的光伏板添加优化器。光伏板的安装位置用一个数组 $pvs$ 表示，$pvs[i] = 1$ 表示该位置有光伏板，$pvs[i]=0$ 表示该位为空。现在需要在空的位置上安装光伏优化器，以便提升所有光伏板的发电效率。(说明：如果光伏板的左边或者右边有优化器的话，就能提升发电的效率)。请计算使所有光伏板都提升发电效率所需要最少的光伏优化器数量，如果不能使所有光伏板都提升发电效率，则返回-1。

注：用例保证输入中一定有光伏板存在

输入描述

第一行一个整数 $N$ ，表示已安装光伏板位置的长度，$1<=N<=10^5$

第二行是长度为 $N$ 的数组 $pvs$ 。$pvs[i]$ 要么为 $1$ ，要么为 $0$ 。

输出描述

最少的优化器的数量

样例1

输入

1
1

输出

-1

说明

没有空位可以安装优化器，无法使所有光伏板都升发电效率

样例2

输入

5
0 1 0 1 0

输出

1

说明

在下标 $2$ 处安装 $1$ 个优化器，可以提升下标 $1$ 和下标 $3$ 处光伏板的发电效率

样例3

输入

4
1 0 0 1

输出

2

说明

需要在下标 $1$ 和下标 $2$ 处分别安装 $1$ 个优化器