Description
一条大河，长为L。有N个石头，现在要移掉M块，求剩下的石头里最小距离最大是多少
Algorithm
并没有什么好方法能直接算，可以考虑二分答案。 对于二分答案，首先是构造ok函数。参数x表示当前的最小距离。 如果当前距离差 < x，那么需要移掉这个石头。最后比较cnt和m判断x是否可行。 第二个需要考虑的是求最小的还是最大的，此题是求最大的，则往大里找。
Code
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std
;
const int N(50000 + 9);
int a
[N
], n
, m
;
int mid(int l
, int r
)
{
return l
+ (r
- l
) / 2;
}
int ok(int x
)
{
int cnt(0), l(0);
for (int i
= 1; i
<= n
+1; i
++) {
if (i
<= n
+1 && a
[i
] - a
[l
] < x
) {
cnt
++;
continue;
}
l
= i
;
}
return cnt
<= m
;
}
int main()
{
int L
;
cin
>> L
>> n
>> m
;
memset(a
, 0, sizeof(a
));
for (int i(1); i
<= n
; i
++) cin
>> a
[i
];
a
[n
+1] = L
;
sort(a
, a
+ n
+ 2);
int l(0), r(L
), ans
;
while (l
<= r
) {
int m(mid(l
, r
));
if (ok(m
)) l
= m
+ 1, ans
= m
;
else r
= m
- 1;
}
cout
<< ans
<< endl
;
}
阅读原文
