11575: 【原1575】river

题目描述

author: ZH 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1575

Description

Sample Input

``````25 5 2
2
11
14
17
21
``````

Sample Output

``````4
``````

Sample Explanation

``````摘走距离起点2和14的两个荷叶，剩下11 17 21，则最小距离为21-17=25-21=4。
``````

Limits

• 对于\(20\%\)的数据，1 <= n, m <= 10,。
• 对于\(50\%\)的数据，1 <= n, m <= 100。
• 对于\(100\%\)的数据，1 <= n, m <= 50000, L <= 10^9。

yyong119's solution

``````#include <iostream>
#include <cstring>
using namespace std;

const int MAX_N = 50010;

int main() {

ios::sync_with_stdio(false);
int l, n, m;
cin >> l >> n >> m;
int a[MAX_N]; a[0] = 0; a[n + 1] = l;
for (int i = 1; i <= n; ++i) cin >> a[i];
int L = 1, R = l, mid, remove;
while (L < R) {
int b[MAX_N];
memcpy(b, a, sizeof(a));
mid = (L + R) >> 1; remove = 0;
for (int i = 1; i <= n + 1; ++i)
if (b[i] - b[i - 1] < mid) {
b[i] = b[i - 1];
if (++remove > m) break;
}
if (remove <= m) L = mid + 1; else R = mid - 1;
}
int k;
for (k = mid + 1; k >= mid - 1; --k) {
int remove = 0;
int b[MAX_N];
memcpy(b, a, sizeof(a));
for (int i = 1; i <= n + 1; ++i)
if (b[i] - b[i - 1] < k) {
b[i] = b[i - 1];
if (++remove > m) break;
}
if (remove <= m) break;
}
cout << k << endl;
return 0;
}
``````