Codeforces 982D(模拟)

Codeforces 982D
题意：有一只鲨鱼每天游$a_i$公里，如果它一天游的距离大于等于$k$，我们就认为它游到了一个新的地方；否则认为它这一天停留在原来的地方。这只鲨鱼到过的地方不会重复。现在给出它$n$天游的距离（每天都不相等），我们要求出一个$k$，满足：
1.鲨鱼停留在每个地方的天数相等。（一天游的距离大于等于$k$时不算停留）。
2.停留过的地方尽可能多。
3.有多个解时$k$取最小值。

很容易想到答案就是某个$a_i+1$，并且没有单调性，不能二分。
另一个角度想，因为每天都不相等，所以我们按照从小到大按顺序将每个点加入，形成几个区间。就变成了区间合并问题。如果加的数左右都没有区间，就新建一个区间。左边或者右边有，扩展区间。都有的话就直接合并区间。然后为了每个区间大小相等，就用当前最长的区间大小乘以当前区间个数如果等于已经插入的点，那么一定每个区间大小相等，更新答案即可。

Codeforces Submission

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define pb push_back
#define sec second
#define fir first
using namespace std;
int n, ai[100000 + 5], lazy[100000 + 5];
pair<int, int > bi[100000 + 5];
void clean() {
    ms(lazy, -1);
}
int solve() {
    clean();
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> ai[i], bi[i].fir = ai[i], bi[i].sec = i;
    sort(bi + 1, bi + 1 + n);
    int maxlen = 0, cnt = 0, ans = 0, maxcnt = 0;
    for (int i = 1; i <= n; i++) {
        if (lazy[bi[i].sec - 1] >= 0 && lazy[bi[i].sec + 1] >= 0) {
            int l = lazy[bi[i].sec - 1], r = lazy[bi[i].sec + 1];
            lazy[bi[i].sec - lazy[bi[i].sec - 1]] += r + 1;
            lazy[bi[i].sec + lazy[bi[i].sec + 1]] += l + 1;
            maxlen = max(maxlen, l + r + 1);
            cnt--;
            lazy[bi[i].sec - 1] = lazy[bi[i].sec + 1] = 0;
        } else if (lazy[bi[i].sec + 1] >= 0) {
            lazy[bi[i].sec] = lazy[bi[i].sec + 1] + 1;
            lazy[bi[i].sec + lazy[bi[i].sec + 1]] = lazy[bi[i].sec];
            maxlen = max(maxlen, lazy[bi[i].sec]);
            lazy[bi[i].sec + 1] = 0;
        } else if (lazy[bi[i].sec - 1] >= 0) {
            lazy[bi[i].sec] = lazy[bi[i].sec - 1] + 1;
            lazy[bi[i].sec - lazy[bi[i].sec - 1]] = lazy[bi[i].sec];
            maxlen = max(maxlen, lazy[bi[i].sec]);
            lazy[bi[i].sec - 1] = 0;
        } else {
            lazy[bi[i].sec] = 1;
            maxlen = max(maxlen, lazy[bi[i].sec]), cnt++;
        }
        if (maxlen * cnt == i) {
            if (cnt > maxcnt) ans = bi[i].fir + 1, maxcnt = cnt;
            else if (cnt == maxcnt) {
                if (ans > bi[i].fir + 1) ans = bi[i].fir + 1;
            }
        }
    }
    cout << ans;
    return 0; 
}
int main() {
    solve();
    return 0;
}