Bzoj 1650(二分+贪心)

BZOJ 1650
Luogu 2855
from: USACO 2006 Dec Sliver(USACO刷题第9题)

最小值最大,显然二分。
二分最小值最大距离,然后贪心处理。
这里我们在头尾各增加一个石头,贪心时先从第一个石头开始记为$l$,然后往后扫描,当前扫描的石头记为$r$,如果$st[r]-st[l]<mid$的话,说明$l, r$中间的石头就算都移走都不能满足最小值最大为$mid$,所以我们一直往后找,找到一个$st[r]-st[l]>=mid$时停下来,移掉中间的所有石头数$r-l-1$,之后和$m$比较即可。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 50000 + 5;
int L, n, m, st[MAXN];
int check(int x) {
int tot = 0, l = 0, r = 1;
while (l<n) {
while (r<n&&st[r]-st[l]<x) r++;
tot += r - l - 1;
l = r;
}
return tot<=m;
}
void clear() {}
void init() {
clear();
for (int i=1;i<=n;i++) scanf("%d", &st[i]);
sort(st+1, st+1+n);
st[0] = 0, st[++n] = L;
}
void solve() {
int ans = 0, l = 0, r = L + 1;
while (l<r) {
int mid = (l+r)>>1;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else r = mid;
}
printf("%d\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d%d%d", &L, &n, &m)==3) init(), solve();
return 0;
}

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