Lexicographic constraints

题目链接：https://atcoder.jp/contests/agc029/tasks/agc029_c

数据范围：略。

题解：

二分是显然的，因为题目具有单调性。

但是怎么验证呢？

显然是贪心地验证，就是要$S_i$是满足条件最小的。

我的办法是维护一棵线段树，因为如果$A_i > A_{i - 1}$的话，只需要在后面加上极小字符。

然后只需要开一棵动态开点的权值线段树，维护这段区间是不是全是极大字符。如果是的话就不可以再变大了。

否则的话就可以，修改的话区间修改单点修改。

但其实不用这么麻烦，我们完全可以用一个$ map $胜任。

即，我们维护出来相当于一个$ mid $进制的东西。$ map $里存的是每一段的结尾，是什么。前面有一段空挡。

$ map $是有序的，随便搞一搞就好。

代码：

#include <bits/stdc++.h>

#define N 200010 

using namespace std;

typedef long long ll;

char *p1, *p2, buf[100000];

#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

int rd() {

	int x = 0, f = 1;

	char c = nc();

	while (c < 48) {

		if (c == '-')

			f = -1;

		c = nc();

	}

	while (c > 47) {

		x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();

	}

	return x * f;

}

int a[N], n;

map <ll, ll> MP;

bool check(int x) {

	MP.clear();

	for (int i = 2; i <= n; i ++ ) {

		if (a[i - 1] >= a[i]) {

			if (x == 1) {

				return false;

			}

			while (!MP.empty()) {

				ll mx = MP.rbegin() -> first;

				if (mx > a[i]) {

					MP.erase(mx);

				}

				else {

					break;

				}

			}

			int j = a[i];

			while (j > 0 && MP[j] + 1 == x) {

				MP.erase(j);

				j -- ;

			}

			if (!j) {

				return false;

			}

			MP[j] ++ ;

		}

	}

	return true;

}

int main() {

	n = rd();

	for (int i = 1; i <= n; i ++ ) {

		a[i] = rd();

	}

	int l = 1, r = n, ans = n;

	while (l <= r) {

		int mid = (l + r) >> 1;

		if (check(mid)) {

			ans = mid;

			r = mid - 1;

		}

		else {

			l = mid + 1;

		}

	}

	cout << ans << endl ;

	return 0;

}

巴特西

[Agc029C]Lexicographic constraints_进制_二分答案_贪心

Lexicographic constraints

最新文章

热门文章