AcWing 3729. 改变数组元素
本文最后更新于501 天前,其中的信息可能已经过时,如有错误请发送邮件到1739584917@qq.com

题目

给定一个空数组 V 和一个整数数组 a1,a2,…,an。

现在要对数组 V 进行 n 次操作。

第 i 次操作的具体流程如下:

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

注意:

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

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

输入格式

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

每组数据第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

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

数据范围

1≤T≤20000,
1≤n≤2×10e5,
0≤ai≤n,
保证一个测试点内所有 n的和不超过 2×10e5。

输入样例:

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

思路:

每次操作都会插入0,所以数组最后的长度是2*n。

可以从后往前扫描,可以使i位置开始往前a[i]长度内变成1

每次更新边界

代码:

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int v[200005],ans[200005];
int t,n;
int main()
{
	
	cin >> t;
	while (t--)
	{
		memset(ans, 0, sizeof(ans));//初始化ans数组
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			cin >> v[i];
		}
		int l = v[n];
		for (int i = n; i >= 1; i--)
		{
			l = max(l, v[i]);//更新边界
			if (l > 0)
			{
				l--;
				ans[i] = 1;
			}
		}
		for (int i = 1; i <= n; i++)
		{
			cout << ans[i] << " ";
		}
		cout << "\n";
	}
	
}
如果觉得本文对您有所帮助,可以支持下博主,一分也是缘
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇