Codeforces 982D(模拟)

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

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

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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;
}

------ 本文结束 ------