侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 22 条评论

目 录CONTENT

文章目录

【差分】改变数组元素

GabrielxD
2023-02-15 / 0 评论 / 0 点赞 / 263 阅读 / 742 字
温馨提示:
本文最后更新于 2023-02-15,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

3729. 改变数组元素 - AcWing题库


给定一个空数组 VV 和一个整数数组 a1,a2,,ana_1,a_2,…,a_n

现在要对数组 VV 进行 nn 次操作。

ii 次操作的具体流程如下:

  1. 从数组 VV 尾部插入整数 00
  2. 将位于数组 VV 末尾的 aia_i 个元素都变为 11 (已经是 11 的不予理会)。

注意:

  • aia_i 可能为 00 ,即不做任何改变。
  • aia_i 可能大于目前数组 VV 所包含的元素个数,此时视为将数组内所有元素变为 11

请你输出所有操作完成后的数组 VV

输入格式

第一行包含整数 TT ,表示共有 TT 组测试数据。

每组数据第一行包含整数 nn

第二行包含 nn 个整数 a1,a2,,ana_1,a_2,…,a_n

输出格式

每组数据输出一行结果,表示所有操作完成后的数组 VV ,数组内元素之间用空格隔开。

数据范围

1T200001 \le T \le 20000 ,
1n2×1051 \le n \le 2 \times 10^5 ,
0ain0 \le a_i \le n ,
保证一个测试点内所有 nn 的和不超过 2×1052 \times 10^5

输入样例:

3
6
0 3 0 0 1 3
10
0 0 0 1 0 5 0 0 0 2
3
0 0 0

输出样例:

1 1 0 1 1 1
0 1 1 1 1 1 0 0 1 1
0 0 0

解题

方法一:差分

思路

该题需要频繁地改变数组中一部分(一个区间)内的数,所以考虑使用差分,但和传统差分不同的是:传统差分一般都是把某个区间上的数加/减一个值,而该题是把某个区间上的数全部变为一个数 1 ,所以在处理完差分数组求前缀和的时候,在前缀和等于 00 时输出 00 其它情况输出均 11

注意:aia_i 大于目前数组 VV 所包含的元素个数,不要越界了,此时视为将数组内所有元素变为 11

代码

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

public class Main {
    static final int N = (int) 2e5 + 10;
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int t = (int) in.nval;
        while (t-- > 0) {
            in.nextToken();
            int n = (int) in.nval;
            int[][] segs = new int[n][2];
            int[] b = new int[n + 1];
            for (int i = 0; i < n; ++i) {
                in.nextToken();
                int x = (int) in.nval;
                if (x != 0) {
                    ++b[Math.max(0, i - x + 1)];
                    --b[i + 1];
                }
            }
            int curr = 0;
            // Java输出太慢了 所以先把答案拼接起来再一起输出
            StringBuilder ans = new StringBuilder();
            for (int i = 0; i < n; ++i) ans.append((curr += b[i]) == 0 ? "0 " : "1 ");
            System.out.println(ans);
        }
    }
}
0

评论区