洛谷 P11388 [COCI 2024/2025 #1] 飞跃 / Skokovi

# [COCI 2024/2025 #1] 飞跃 / Skokovi

## 题目背景

译自 [COCI 2024/2025 #1](https://hsin.hr/coci/) T2。$\texttt{5s,0.5G}$。满分为 $75$。

## 题目描述

有 $n$ 朵花，此外有一个正整数 $k$。第 $i$ 朵花的高度为 $a_i$。

一开始，Filip 在第 $1$ 朵花上。

当她在第 $i$ 朵花上时，她可以飞跃到第 $j$ 朵花上，当且仅当：

- $i\lt j$；
- $|a_i-a_j|\le k$。

Filip 想要知道她能够飞跃到哪些花上。

## 输入格式

第一行，两个正整数 $n,k$。

第二行，$n$ 个正整数 $a_1,a_2,\cdots,a_n$。

## 输出格式

$n$ 个整数，第 $i$ 个整数为 $\texttt{0}$，代表不能跳到第 $i$ 朵花上；第 $i$ 个整数为 $\texttt{1}$，代表可以跳到第 $i$ 朵花上。

## 样例 #1

### 样例输入 #1

```
5 2
5 4 8 7 2
```

### 样例输出 #1

```
1 1 0 1 1
```

## 样例 #2

### 样例输入 #2

```
5 3
10 15 14 8 9
```

### 样例输出 #2

```
1 0 0 1 1
```

## 提示

对于 $100\%$ 的数据，保证：

- $1\le n\le 2\times 10^5$；
- $1\le a_i,k\le 10^9$。

| 子任务编号 | $n\le$ |  特殊性质 | 得分 |  
| :--: | :--: | :--: |:--: | 
| $ 1 $    | $2\times 10^5$ | A    |   $ 25 $   |  
| $ 2 $    | $10^3$ |   |  $ 25 $   |  
| $ 3 $    | $2\times 10^5$  | | $ 25 $   |

- 特殊性质 A：$\forall 1\le i\lt n$，$a_i\lt a_{i+1}$。

#include <iostream>
#include <algorithm>

using namespace std;

int n, k;
int a[200100];


int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	int min_ = a[0];
	int max_ = a[0];
	for (int i = 0; i < n; i++) {
		if(min_-k<=a[i]&&max_+k>=a[i]){
		//根据题目的绝对值的范围可知当a[i]满足:
		//min-k<=a[i]<=max+k 符合题意下标1
			cout<<"1 ";
			min_=min(min_,a[i]);//更迭标记的最小值
			max_=max(max_,a[i]);//更迭标记的最大值	
		}else{
			cout<<"0 ";
		}
	}

	return 0;
}