01序列

思路

题目说的是：给你一个只含 0 和 1 的数组，原始数组里的 1 已经互不相邻了，现在问你能不能把其中 n 个 0 改成 1，改完之后所有的 1 仍然互不相邻？

那怎么想？既然要尽可能多地放 1，那就贪心呗——从左到右扫一遍，遇到一个 0，只要它左右邻居都不是 1，就把它变成 1。为什么贪心是对的？因为越早放 1，最多只会"挡住"右边紧挨着的那个位置，而如果你跳过当前位置去放右边，效果不会更好，反而可能更差。换句话说，能放就放，不会亏。

具体做法：

  1. 从左到右遍历数组，对每个位置 i，如果 a[i] == 0：

- 检查左边：i == 0 或者 a[i-1] == 0

- 检查右边：i == len-1 或者 a[i+1] == 0

- 两边都满足，就把 a[i] 改成 1，计数器 +1

  1. 最后看计数器是否 >= n，是就输出 true，否则 false。

举个例子：1 0 0 0 1，n=1。扫到第二个位置（下标1），左边是1，不行；第三个位置（下标2），左边是0右边是0，放！变成 1 0 1 0 1，计数器=1 >= 1，输出 true。如果 n=2 呢？放完下标2之后，下标1左边是1不行，下标3右边是1不行，只能放1个，1 < 2，输出 false。

代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int len;
    cin >> len;
    vector<int> a(len);
    for (int i = 0; i < len; i++) cin >> a[i];
    int n;
    cin >> n;

    int cnt = 0;
    for (int i = 0; i < len; i++) {
        if (a[i] == 0) {
            bool left = (i == 0 || a[i - 1] == 0);
            bool right = (i == len - 1 || a[i + 1] == 0);
            if (left && right) {
                a[i] = 1;  // 贪心：能放就放
                cnt++;
            }
        }
    }

    cout << (cnt >= n ? "true" : "false") << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        int[] a = new int[len];
        for (int i = 0; i < len; i++) a[i] = sc.nextInt();
        int n = sc.nextInt();

        int cnt = 0;
        for (int i = 0; i < len; i++) {
            if (a[i] == 0) {
                boolean left = (i == 0 || a[i - 1] == 0);
                boolean right = (i == len - 1 || a[i + 1] == 0);
                if (left && right) {
                    a[i] = 1;  // 贪心：能放就放
                    cnt++;
                }
            }
        }

        System.out.println(cnt >= n ? "true" : "false");
    }
}

length = int(input())
a = list(map(int, input().split()))
n = int(input())
cnt = 0
for i in range(length):
    if a[i] == 0:
        left = (i == 0 or a[i - 1] == 0)
        right = (i == length - 1 or a[i + 1] == 0)
        if left and right:
            a[i] = 1
            cnt += 1
print("true" if cnt >= n else "false")

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const len = parseInt(lines[0]);
    const a = lines[1].split(' ').map(Number);
    const n = parseInt(lines[2]);
    let cnt = 0;
    for (let i = 0; i < len; i++) {
        if (a[i] === 0) {
            const left = (i === 0 || a[i - 1] === 0);
            const right = (i === len - 1 || a[i + 1] === 0);
            if (left && right) {
                a[i] = 1;
                cnt++;
            }
        }
    }
    console.log(cnt >= n ? "true" : "false");
});

复杂度分析

  • 时间复杂度: ，其中 是数组长度，只需扫一遍。
  • 空间复杂度: ，存储数组本身。

小结

这题就是经典的贪心放置问题。核心想法很朴素：从左到右扫，当前位置是 0 且左右都不是 1，那就放。不需要回溯、不需要 dp，一次遍历搞定。关键点在于理解「能放就放不会亏」——提前占位不会比延后放更差，因为你最多只影响右边紧邻的一个格子。