首页 > 其他分享 >CF982D

CF982D

时间:2022-10-16 06:55:05浏览次数:39  
标签:int siz mx fa num CF982D find

*1900 不会做了。。

考虑将所有数从小到大排序后顺次插入,用并查集维护。

需要维护以下几个东西:区间的总数量,最长区间的长度,最长区间的个数。

当最长区间的个数等于区间的总数量时,更新答案。

具体细节看代码。

Code:

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair <int, int> pii;
const int N = 100005;
int n;
pii a[N];
int fa[N], siz[N];
int mx, num, tot;
bool vis[N];
int ans1, ans2;

int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) { x = find(x), y = find(y); if (x == y) return; siz[x] += siz[y], fa[y] = x; }

void add(int x) {
	vis[x] = 1;
	if (vis[x - 1]) --tot, num -= siz[find(x - 1)] == mx, merge(x, x - 1);
	if (vis[x + 1]) --tot, num -= siz[find(x + 1)] == mx, merge(x, x + 1);
	++tot; int t = siz[find(x)];
	if (mx < t) mx = t, num = 1;
	else if (mx == t) ++num;
}

int main() {
	scanf("%d", &n);
	for (int i = 1, x; i <= n; ++i) scanf("%d", &x), a[i] = pii(x, i), fa[i] = i, siz[i] = 1;
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++i) {
		add(a[i].se);
		if (num == tot && (num > ans1 || (num == ans1 && a[i].fi + 1 < ans2)))
			ans1 = num, ans2 = a[i].fi + 1;
	}
	printf("%d", ans2);
	return 0;
}

标签:int,siz,mx,fa,num,CF982D,find
From: https://www.cnblogs.com/Kobe303/p/16795578.html

相关文章