P7285 修改数组

calendar May 4, 2026 · 6 分钟阅读 · 数学  ·
分享到: linkedin copy

文章目录

题目信息

字段 内容
题号 P7285
难度 红题（入门）
知识点 贪心、模拟

题目描述

给定一个长度为 n、元素只含 0 或 1 的数组。

你可以进行若干次操作：选择若干个值为 0 的元素，将其修改为 1（不能为 1 改 0）。

记：

  • x = 修改后数组中最长连续 1 子段的长度（若全为 0 则 x = 0）
  • y = 被修改的元素的个数

求 x - y 的最大值，并输出一种能达到该最大值的修改后的数组（如有多种方案，任意输出一种即可）。

输入格式：

T
（对于每组数据）
n
a1 a2 ... an

第一行一个整数 T，表示测试数据组数。 每组数据第一行一个整数 n，第二行 n 个整数 a_1 ... a_n（保证为 0 或 1）。

输出格式： 共 2 × T 行，每 2 行表示一组数据：

  • 第一行：一个整数，表示 x - y 的最大值；
  • 第二行：n 个整数（0 或 1），表示修改后的数组。

样例输入：

2
3
0 1 0
5
1 0 0 1 1

样例输出：

1
1 1 1
3
1 1 1 1 1

数据范围： 1 ≤ T ≤ 10，1 ≤ n ≤ 10^5，各测试点 n 之和不超过 10^5。保证输入均为合法 0 或 1。

解题思路

核心观察

这道题最妙的地方在于：把某个 0 改成 1，对 x - y 的值没有影响！

证明很简单：

  • 修改前：x = L，y = k
  • 把一个 0 改成 1：这个 0 变成 1 后，可能让某段连续 1 变长，假设最长连续 1 子段长度增加了 Δx（Δx ≥ 0）
  • 修改后：x' = x + Δx，y' = y + 1
  • x' - y' = (x + Δx) - (y + 1)

等等，这样分析比较复杂。换个角度思考：

关键结论：把所有的 0 都改成 1，是最优策略之一。

理由：

  • 改一个 0 为 1：y 增加 1；同时这个 1 可能连接左右两段 1，让 x 增加。
  • 最极限情况：把所有数都改成 1，则 x = n。
  • 此时 x - y = n - (n - {原1的个数}) = {原1的个数}。
  • 这个值恰好等于：不修改任何元素时，x - y = {最长连续1子段长度} 的上界（因为原1的个数 ≥ 最长连续1子段长度）。

实际上可以证明：x - y 的最大值 = 原数组中 1 的总个数。

证明思路：

  • 设原数组中 1 的个数为 c_1。
  • 若把所有 0 改成 1：x = n，y = n - c_1，x - y = c_1。
  • 若不做任何修改：x = {最长连续1子段长度} ≤ c_1，y = 0，x - y ≤ c_1。
  • 若只改部分：0 改 1 过程中 x 的增长不超过 y 的增长（每次操作 y 必然 +1，x 至多增加该 0 连接的两侧 1 段长度之和 +1，但这部分 1 原本就存在）。
  • 综上，x - y 的最大值就是 c_1。

算法流程

读入 T
对于每组数据：
    读入 n
    统计数组中 1 的个数，记为 ans
    输出 ans
    输出 n 个 1（把数组全部改为 1 是一种合法方案）
  • 时间复杂度：O(T × n)，各测试点 n 之和 ≤ 10^5，完全可行。
  • 空间复杂度：O(1)（无需储存数组，边读边统计即可）。

完整代码（C++）

// P7285 修改数组 - 洛谷
// 知识点：贪心、模拟
// 算法：把所有 0 改成 1，x-y 的最大值 = 原数组中 1 的个数
// 作者：朱雀

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

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

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        int ans = 0;  // 原数组中 1 的个数
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            if (x == 1) {
                ans++;
            }
        }

        // 输出 x-y 的最大值
        cout << ans << "\n";

        // 输出修改后的数组（全为 1 是一种合法方案）
        for (int i = 0; i < n; i++) {
            cout << "1 ";
        }
        cout << "\n";
    }

    return 0;
}

关键代码讲解

为什么要统计「1 的个数」？

这是本题最巧妙的数学结论：把任意个 0 改成 1 后，x - y 的值不会改变（或者说，最大值恰好等于原数组 1 的个数）。

直观理解：每改一个 0→1，你付出了 1 的代价（y 增加 1），但同时可能让连续 1 段变长。最理想情况是全改成 1，此时 x = n，y = n - c_1，相减得 c_1。

为什么不需要存数组？

因为只需要知道 1 的个数，不需要根据原数组构造答案（全输出 1 就是合法方案）。所以边读边统计即可，空间复杂度 O(1)。

易错点 / 注意事项

  • ⚠️ 每组数据输出 2 行：第一行是 x-y 的最大值，第二行是修改后的数组。
  • ⚠️ 末尾空格：洛谷一般允许行末有空格，但最好养成习惯，最后一个元素单独处理（本题不要求，输出 1 重复 n 次后换行即可）。
  • ⚠️ 多测重置：用 while (t--) 结构自然重置，不要依赖全局变量。
  • ⚠️ 用 \n 而非 endl：防止大量输出时频繁刷新缓冲区。

其他语言解法

Python

Python 代码如下（遵循 PEP 8 规范）：

# P7285 修改数组 - 洛谷
# 知识点：贪心、模拟
# 算法：把所有 0 改成 1，x-y 的最大值 = 原数组中 1 的个数


def solve() -> None:
    t = int(input().strip())
    for _ in range(t):
        n = int(input().strip())
        arr = list(map(int, input().split()))
        ans = sum(arr)  # 1 的个数
        print(ans)
        print(" ".join(["1"] * n))


if __name__ == "__main__":
    solve()

Java

⚠️ 重要：Scanner 在洛谷等 OJ 平台下内存占用极高，容易 MLE。请务必使用 BufferedInputStream 手动解析输入。

// P7285 修改数组 - 洛谷
// 知识点：贪心、模拟
// 算法：把所有 0 改成 1，x-y 的最大值 = 原数组中 1 的个数

import java.io.*;
import java.util.*;

public class Main {
    // 高速字节流输入，避免 Scanner 的高内存开销
    private static final class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream in) {
            this.in = in;
        }

        private int readByte() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        int nextInt() throws IOException {
            int c, sign = 1, val = 0;
            do {
                c = readByte();
            } while (c <= ' ' && c != -1);
            if (c == '-') {
                sign = -1;
                c = readByte();
            }
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = readByte();
            }
            return val * sign;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder out = new StringBuilder();
        int t = fs.nextInt();

        while (t-- > 0) {
            int n = fs.nextInt();
            int ans = 0;
            for (int i = 0; i < n; i++) {
                if (fs.nextInt() == 1) {
                    ans++;
                }
            }
            out.append(ans).append('\n');
            for (int i = 0; i < n; i++) {
                out.append('1');
                if (i < n - 1) out.append(' ');
            }
            out.append('\n');
        }
        System.out.print(out.toString());
    }
}

Go

Go 代码如下（遵循 gofmt 规范）：

// P7285 修改数组 - 洛谷
// 知识点：贪心、模拟
// 算法：把所有 0 改成 1，x-y 的最大值 = 原数组中 1 的个数

package main

import (
    "bufio"
    "fmt"
    "os"
    "strings"
)

func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()

    var t int
    fmt.Fscan(in, &t)

    for i := 0; i < t; i++ {
        var n int
        fmt.Fscan(in, &n)
        ans := 0
        for j := 0; j < n; j++ {
            var x int
            fmt.Fscan(in, &x)
            if x == 1 {
                ans++
            }
        }
        fmt.Fprintln(out, ans)
        fmt.Fprintln(out, strings.Repeat("1 ", n-1)+"1")
    }
}

JavaScript (Node.js)

JavaScript 代码如下：

// P7285 修改数组 - 洛谷
// 知识点：贪心、模拟
// 算法：把所有 0 改成 1，x-y 的最大值 = 原数组中 1 的个数

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let t = -1;
let currentCase = 0;
let n = 0;

rl.on("line", function (line) {
    if (t < 0) {
        t = parseInt(line.trim());
        return;
    }
    if (n === 0) {
        n = parseInt(line.trim());
        return;
    }
    const arr = line.trim().split(" ").map(Number);
    const ans = arr.reduce((sum, x) => sum + x, 0); // 1 的个数
    console.log(ans);
    console.log("1 ".repeat(n).trim());
    currentCase++;
    if (currentCase < t) {
        n = 0; // 准备读下一组的 n
    }
});

附：算法概念介绍

贪心算法（Greedy Algorithm）

什么是贪心？

贪心算法的核心思想是：每一步都做出当前看起来最优的选择，期望最终得到全局最优解。

就像一个贪心的人挑水果——每看到一个比别人手里更好的，就立刻换掉手里那个，不管以后会不会后悔。

经典例子：找零问题

用最少的纸币凑出 37 元，面值有 1、5、20、50 元。

贪心策略：每次都选不超过剩余金额的最大面值。

  • 37 → 选 20，剩 17
  • 17 → 选 5，剩 12 → 再选 5，剩 7
  • 7 → 选 5，剩 2
  • 2 → 选 1，剩 1 → 再选 1

用掉：20 + 5 + 5 + 5 + 1 + 1 = 6 张（最优）。

贪心一定对吗？

不一定！贪心不保证全局最优，只有在问题满足「贪心选择性质」时才成立。

反例：如果面值改为 1、15、25 元，凑 30 元：

  • 贪心：25 + 1×5 = 6 张
  • 最优：15 × 2 = 2 张

本题为什么不是贪心？

我们直接推导出「全改成 1」是最优解，没有"一步步做选择"的过程，所以不属于贪心算法。

模拟算法（Simulation）

什么是模拟？

模拟算法是最"老实"的算法——题目让你做什么，你就一步步照着做，不偷懒、不找捷径。

就像按照菜谱做菜：第一步切菜、第二步下油、第三步翻炒……严格按步骤来，最后端出来的菜就是对题目的"模拟"。

经典例子：约瑟夫问题

n 个人围成一圈，从第一个人开始报数，报到 k 的人出圈，下一个人重新从 1 开始报数。求最后剩下的人。

模拟做法：用一个数组记录每个人是否还在圈内，每次找到第 k 个还在的人，将其标记为出圈，直到只剩一个人。

模拟的优缺点

优点 缺点
思路直接，不容易写错 如果数据规模大，可能超时
适合入门，几乎所有题都能"硬算" 不是优雅的解法

本题为什么不是模拟？

模拟的做法应该是：真的去"修改数组"，每次把一个 0 改成 1，然后计算新的 x 和 y，比较所有方案……但这太慢了（指数级）。我们跳过了模拟过程，直接数学推导，所以也不是模拟。