题解 | #01序列#_牛客博客

题目链接

01序列

题目描述

给定一个只包含0和1的数组 metrix，已知数组中初始的1都不相邻。现在需要将数组中的 $n$ 个0替换成1，请问能否在操作后依然保证数组中所有的1都不相邻？

解题思路

这是一个典型的贪心问题。为了判断是否能放下 $n$ 个新的1，我们首先需要计算出，在保持“1不相邻”规则的前提下，这个数组最多能容纳多少个新的1。

贪心策略 我们的目标是最大化可以新放置的1的数量。策略应该是：从左到右遍历数组，只要遇到一个可以合法放置1的位置，就立即放置一个。

合法位置的判断 一个位置 i 是合法的，当且仅当以下三个条件同时满足：

该位置本身是0 (metrix[i] == 0)。
它的左边没有1。即 i == 0 (是数组的第一个位置) 或者 metrix[i-1] == 0。
它的右边没有1。即 i == m-1 (是数组的最后一个位置) 或者 metrix[i+1] == 0。

算法步骤

初始化一个计数器 max_placable 为0，用来记录最多可以新放置的1的数量。
遍历数组 metrix，从头到尾检查每一个位置 i。
对于每个位置 i，判断它是否是一个合法位置（如上所述）。
如果 i 是一个合法位置：
- 我们就决定在这里放置一个1。将 max_placable 加1。
- 关键一步：为了确保我们后续的判断是正确的，我们需要模拟“放置”这个行为。最简单的方法是直接修改原数组（或其副本），将 metrix[i] 的值变为1。这样，当我们检查下一个位置 i+1 时，它的左邻居 metrix[i] 已经是1了，它自然就不是一个合法位置了。
遍历结束后，max_placable 就代表了我们最多能新放置的1的数量。
最后，比较 max_placable 和题目要求的 $n$ 。如果 max_placable >= n，说明我们有足够的位置来放置 $n$ 个1，答案是 true。否则，答案是 false。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int m;
    cin >> m;
    vector<int> metrix(m);
    for (int i = 0; i < m; ++i) {
        cin >> metrix[i];
    }
    int n;
    cin >> n;
    
    int max_placable = 0;
    for (int i = 0; i < m; ++i) {
        // 判断位置i是否可以放1
        if (metrix[i] == 0) {
            bool left_ok = (i == 0) || (metrix[i - 1] == 0);
            bool right_ok = (i == m - 1) || (metrix[i + 1] == 0);
            
            if (left_ok && right_ok) {
                metrix[i] = 1; // 放置一个1
                max_placable++;
            }
        }
    }
    
    if (max_placable >= n) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int[] metrix = new int[m];
        for (int i = 0; i < m; i++) {
            metrix[i] = sc.nextInt();
        }
        int n = sc.nextInt();
        
        int maxPlacable = 0;
        for (int i = 0; i < m; i++) {
            // 判断位置i是否可以放1
            if (metrix[i] == 0) {
                boolean leftOk = (i == 0) || (metrix[i - 1] == 0);
                boolean rightOk = (i == m - 1) || (metrix[i + 1] == 0);
                
                if (leftOk && rightOk) {
                    metrix[i] = 1; // 放置一个1
                    maxPlacable++;
                }
            }
        }
        
        if (maxPlacable >= n) {
            System.out.println("true");
        } else {
            System.out.println("false");
        }
    }
}

import sys

def solve():
    m = int(sys.stdin.readline())
    metrix = list(map(int, sys.stdin.readline().split()))
    n = int(sys.stdin.readline())
    
    max_placable = 0
    for i in range(m):
        # 判断位置i是否可以放1
        if metrix[i] == 0:
            left_ok = (i == 0) or (metrix[i - 1] == 0)
            right_ok = (i == m - 1) or (metrix[i + 1] == 0)
            
            if left_ok and right_ok:
                metrix[i] = 1  # 放置一个1
                max_placable += 1
                
    if max_placable >= n:
        print("true")
    else:
        print("false")

solve()

算法及复杂度

算法：贪心
时间复杂度：我们只需要对长度为 $m$ 的数组进行一次完整的遍历。因此，总时间复杂度为 $\mathcal{O}(m)$ 。
空间复杂度：我们需要存储输入的数组。因此，空间复杂度为 $\mathcal{O}(m)$ 。