题目描述

简单来说就是一个长度为 $n$ 序列 $a$，如果 $a_{i}$ 之前没有被取过，并且在取出 $a_{i}$ 之前已经取出了的数的个数不小于 $a_{i}$，才可以把 $a_{i}$ 取出。问经过几次这样的操作，才能把序列的数全部取完，不能输出 -1。

解题思路

很明显可以想到线段树（不懂看这里），我们可以用一颗线段树来维护区间内的最小值。

用一个变量记录取了多少数，在修改的过程中，如果该区间的最小值小于这个变量，那就递归进去将里面所有小于这个变量的数取出，并修改为 INF。最后，如果整棵树的最小值就是 INF，说明全部取完了，输出即可。

反之，输出 -1。

复杂度 $O(n \operatorname{log} n)$。

code

# include <bits/stdc++.h>
# define int long long
using namespace std;
const int INF = 2147483647;
const int N = 5e5 + 10;
int v[N], cnt;
int a[4 * N];
void build(int now, int l, int r) {
	if (r == l) {
		a[now] = v[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(now << 1, l, mid);
	build(now << 1 | 1, mid + 1, r);
	a[now] = min(a[now << 1], a[now << 1 | 1]);
}
void update(int now, int l, int r, int x) {
	if (l == r) {
		a[now] = x;
		cnt++;
		return;
	}
	int mid = (l + r) >> 1;
	if (a[now << 1] <= cnt) {
		update(now << 1, l, mid, x);
	}
	if (a[now << 1 | 1] <= cnt) {
		update(now << 1 | 1, mid + 1, r, x);
	}
	a[now] = min(a[now << 1], a[now << 1 | 1]);
}
signed main() {
	int n, d;
	cin >> d >> n;
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}
	build(1, 1, n);
	int ret = 0;
	while (1) {
		ret++;
		update(1, 1, n, INF);
		if (a[1] == INF) {
			break;
		}
		if (ret >= n) {
			printf("-1");
			return 0;
		}
	}
	printf("%lld", ret);
	return 0;
}