bzoj5397 circular 随机化(

题目大意

给定一个环，环上有一些线段，试选出最多的线段

题解：

提醒：这可能是一篇非常欢乐的题解

我们考虑倍长环，然后断环为链

我们考虑枚举开头的线段，然后做一次贪心

这样子的复杂度根据实现的不同是\(O(n^2 \log n)\)或者\(O(n^2)\)

不妨假设我们不知道倍增能优化，我们考虑答案的构成，记答案为\(B\)

如果\(B < \sqrt n\)，那么我们只需要每次跳\(B\)次就可以出解

如果\(B > \sqrt n\)，那么我们随机取\(\frac{n}{B}\)个线段作为端点，然后取最优值

这样子，我们就得到了一个看起来完全不对劲的\(O(n \sqrt n)\)的算法

但是人都是懒惰的，我们考虑直接用第二种方法

经过实践，实际上只要取\(2\)个线段作为端点就足够\(A\)掉本题了

复杂度\(O(n \log n)\)，虽然正确性完全无法保证呢

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define ri register int

#define rep(io, st, ed) for(ri io = st; io <= ed; io ++)

#define drep(io, ed, st) for(ri io = ed; io >= st; io --)

#define gc getchar

inline int read() {

	int p = 0, w = 1; char c = gc();

	while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); }

	while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc();

	return p * w;

}

const int sid = 2e5 + 5;

int n, m, tot;

int L[sid], R[sid];

struct seg {

	int l, r;

	seg() {}

	seg(int _l, int _r) : l(_l), r(_r) {}

	friend bool operator < (seg a, seg b)

	{ return a.r > b.r; }

} A[sid];

priority_queue <seg> q;

inline int solve(int o) {

	int ret = 0, nr = -1;

	rep(i, 1, tot)

		if(A[i].l >= L[o] && A[i].r <= L[o] + m) q.push(A[i]);

	while(!q.empty()) {

		seg B = q.top(); q.pop();

		if(B.l < nr) continue;

		nr = max(nr, B.r); ret ++;

	}

	return ret;

}

int main() {

	m = read(); n = read();

	rep(i, 1, n) {

		int l = read(), r = read();

		L[i] = l; R[i] = r;

		if(l > r) A[++ tot] = seg(l, r + m);

		else {

			A[++ tot] = seg(l, r);

			A[++ tot] = seg(l + m, r + m);

		}

	}

	int ans = 0, k = 2;

	for(ri i = 1; i <= n; i += n / k) ans = max(ans, solve(i));

	printf("%d\n", ans);

	return 0;

}

巴特西

bzoj5397 circular 随机化(

最新文章

热门文章