AcWing 3729. 改变数组元素
原题链接
中等
作者:
Ccoconut
,
2023-03-23 19:57:36
,
所有人可见
,
阅读 106
算法1
暴力算法(10/10)
Java 代码
import java.io.*;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(in.readLine());
while(t-- > 0) {
int n = Integer.parseInt(in.readLine());
int []a = new int[n+10];
int []V = new int[n+10];
String[] s = in.readLine().split(" ");
for(int i = 1;i <= n;i++) {
a[i] = Integer.parseInt(s[i-1]);
if(a[i] == 0) continue;
else if(a[i] < i ) {
Arrays.fill(V, i-a[i]+1,i+1,1);
}
else {
Arrays.fill(V,1,i+1, 1);
}
}
for(int i = 1;i <=n;i++ ) {
System.out.print(V[i]+" ");
}
System.out.println();
}
}
}
算法2
差分
Java代码
import java.io.*;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(in.readLine());
while(t-- > 0) {
int n = Integer.parseInt(in.readLine());
int []a = new int[n+10];
int []V = new int[n+10];
String[] s = in.readLine().split(" ");
int []b = new int[n+10];
for(int i = 1;i <= n;i++) {
a[i] = Integer.parseInt(s[i-1]);
if(a[i] == 0) continue;
else if(a[i] < i) {
//需要操作的范围是[i-a[i]+1,i]
b[i-a[i]+1] +=1;
b[i+1] -= 1;
}
else {
//需要操作的范围是[1,i]
b[1]+=1;
b[i+1]-=1;
}
}
for(int i = 1;i <=n;i++) {
b[i] = b[i] + b[i-1];
if(b[i]>=1) V[i] = 1;
}
for(int i = 1;i <=n;i++ ) {
System.out.print(V[i]+" ");
}
System.out.println();
}
}
}