题解：P14132 【MX-X22-T3】「TPOI-4C」Another MEX Problem

彻底怒了，这题我调了超级久。

暴力思路很简单，就是我们把当前所有数排个序，然后如果相邻两个数

x,y

满足

y-x>k

，则我们需要用

\lfloor \frac{y-x-1}{k}\rfloor

次操作把他填满，当然在边界的时候不一定能填满，特判即可。

考虑怎么优化这个过程，首先把当前数排序以及计算相邻两数的差值可以用 set 优化，然后因为答案单调不减，我们在上一次可以填满的位置，在这一次一定也能填满，于是再开一个 set 记录我们需要填满的位置，然后从上一个填满的位置继续暴力计算还能填满到哪个位置。

常数超级大，代码超级难写。

Code

CPP

#include <bits/stdc++.h>
using namespace std;
int a[1000005];

struct node {
	int x, y;
	inline friend bool operator<(node l, node r) {
		if (l.x != r.x)
			return l.x < r.x;
		return l.y < r.y;
	}
	inline node(int aa = 0, int bb = 0) {
		x = aa;
		y = bb;
	}
};
int wan, yong, dang, now;

signed main() {
	int t, n, m, k, z1, z2;
	scanf("%d", &t);
	set<int>s;
	set<node>ss;
	auto it = s.begin();
	auto itt = ss.begin();
	while (t--) {
		scanf("%d%d%d", &n, &m, &k);
		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		now = 0;
		s.clear(), ss.clear();
		s.insert(-1);

		wan = -2, yong = 0, dang = -1;
		for (int i = 1; i <= n; i++) {
			if (s.find(a[i]) == s.end()) {
				s.insert(a[i]);
				it = s.find(a[i]);
				z1 = *(--it);
				it++;
				it++;
				z2 = -100;
				if (it != s.end())
					z2 = *(it);
				if (z2 >= 0)
					ss.erase(node(z1, (z2 - z1 - 1) / k));
				if (z2 - z1 > k && z2 >= 0) {
					now -= (z2 - z1 - 1) / k;
					if (wan >= z1)
						yong -= (z2 - z1 - 1) / k;
				}
				ss.insert(node(z1, (a[i] - z1 - 1) / k));
				if (a[i] - z1 > k) {
					now += (a[i] - z1 - 1) / k;
					if (wan >= z1)
						yong += (a[i] - z1 - 1) / k;
				}
				if (z2 >= 0)
					ss.insert(node(a[i], (z2 - a[i] - 1) / k));
				if (z2 - a[i] > k && z2 >= 0) {
					now += (z2 - a[i] - 1) / k;
					if (wan >= z1)
						yong += (z2 - a[i] - 1) / k;
				}
				if (z2 - z1 > k && z2 >= 0 && wan >= z1)
					wan = max(wan, a[i]);
			}
			if (m >= now) {
				it = s.end();
				it--;
				itt = ss.end();
				if (itt != ss.begin()) {
					wan = (*(--itt)).x;
					yong = now;
					dang = (*it);
				}
				printf("%lld ", ((*it) + 1LL * (m - now) * k + 1));
			} else {
				int zz = yong, no = dang;
				itt = ss.lower_bound(node(dang, 0));
				while (itt != ss.end() && (*itt).x == wan)
					itt++;
				while (1) {
					if (itt == ss.end())
						break;
					node x = *itt;
					int kk = min(x.y, m - zz);
					no = x.x + min(x.y, m - zz) * k;
					zz += min(x.y, m - zz);
					if (zz == m && kk != x.y)
						break;
					itt++;
					wan = x.x;
					if (!x.y)
						ss.erase(x);
					yong = zz;
					dang = no;
				}
				printf("%d ", no + 1);
			}
		}
		puts("");
	}
}
/*
1
8 4 1
3 12 7 8 11 0 10 1
*/

题解：P14132 【MX-X22-T3】「TPOI-4C」Another MEX Problem

文章操作

相关推荐

评论

题解：P14132 【MX-X22-T3】「TPOI-4C」Another MEX Problem