luogu4064

题目描述

从给定的个区间中选出个，对每个区间中的每个数加，要求使得操作完成之后的序列中的最小值最大，求最大的最小值。

解题思路

最小的最大，立刻考虑到二分答案。

考虑check的编写。

记每个位置需要被操作的次数为。

我们考虑用两个堆来解决。堆1用来保存左端点坐标满足的所有区间，堆2用来保存当前正在使用的所有区间。

处理到位置的时候，我们首先需要将的所有区间加入到堆1中，之后将不符合条件的区间从堆2中移走。

如果堆2此时的大小满足，那么该位置条件满足。

反之，我们需要加入新的区间。我们从堆1中不断的取出区间加入堆2，这些区间的右端点单调递减。我们如此贪心的目的在于使的每个区间都能发挥其最大价值。如果我们无法取出新区间或者取出的区间的右端点已经小于i了，那么必然不存在答案，返回false。如果选用的区间个数大于，那么也不行，返回false。只需要扫一遍即可。

时间复杂度。

附代码

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
const int N = 2e5 + 5;
int a[N];
struct Seg {
	int l, r;
} seg[N];
bool cmp(Seg x, Seg y) {
	return x.l < y.l || (x.l == y.l && x.r < y.r);
}
struct CmpH {
	bool operator() (const Seg x, const Seg y) const {
		return x.r < y.r;
	}
};
struct CmpL {
	bool operator() (const Seg x, const Seg y) const {
		return x.r > y.r;
	}
};
std::priority_queue <Seg, std::vector<Seg>, CmpH> pqh;
std::priority_queue <Seg, std::vector<Seg>, CmpL> pql;
int check(int x, int n, int m, int k, int val) {
	while (!pqh.empty()) pqh.pop();
	while (!pql.empty()) pql.pop();
	static int tmp[N];
	for (int i = 1; i <= n; ++i) {
		if (x > a[i]) {
			tmp[i] = (x - a[i]) / val;
			if ((x - a[i]) % val) ++tmp[i];
		}
		else tmp[i] = 0;
	}
	int pt = 1, cnt = 0;
	for (int i = 1; i <= n; ++i) {
		while (pt <= m && seg[pt].l == i) pqh.push(seg[pt]), ++pt;
		while (!pql.empty() && pql.top().r < i) pql.pop();
		if (pql.size() >= tmp[i]) continue;
		else {
			while (pql.size() < tmp[i]) {
				if (pqh.empty()) return 0;
				int r = pqh.top().r;
				if (r >= i) pql.push(pqh.top()), pqh.pop(), ++cnt;
				else return 0;
			}
			if (cnt > k) return 0;
		}
	}
	return 1;
}
int bs(int n, int m, int k, int val) {
	int l = 1, r = 3e8;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid, n, m, k, val)) l = mid + 1;
		else r = mid - 1;
	}
	return l - 1;
}
void work() {
	int n, m, k, val;
	scanf("%d%d%d%d", &n, &m, &k, &val);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &seg[i].l, &seg[i].r);
	}
	std::sort(seg + 1, seg + m + 1, cmp);
	printf("%d\n", bs(n, m, k, val));
}
int main() {
	int T;
	scanf("%d", &T);
	while (T--) work();
	return 0;
}