*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