时间限制 1000 ms 内存限制 64 MB
题目描述
有一条河，河中间有一些石头，已知石头的数量和相邻两块石头之间的距离。现在可以移除一些石头，问最多移除m块石头后（首尾两块石头不可以移除），相邻两块石头之间的距离的最小值最大是多少。
输入数据
第一行输入两个数字，n（2<=n<=1000）为石头的个数，m（0<=m<=n-2）为可移除的石头数目 随后n-1个数字，表示顺序和相邻两块石头的距离d（d<=1000）
输出数据
输出最小距离的最大值
样例输入
4 1 1 2 3
样例输出
3
#include <iostream> #include <algorithm> #include <cmath> using namespace std; int n = 0, m = 0, dis[1001] = { 0 }; int tmpdis = 0; int maxdis = 0; int Validate(int d) { int k = m; int st = 1; for (int en = 2; en <= n;) { int disCur = dis[en] - dis[st]; while (disCur < d) { k--; en++; if (k < 0) { return 0; } if (en > n) { if (st == 1) { return 0; } else { return 1; } } disCur = dis[en] - dis[st]; } st = en; en++; } return 1; } int main() { cin >> n >> m; for (int i = 2; i <= n; i++) { cin >> tmpdis; dis[i] = dis[i - 1] + tmpdis; maxdis = dis[i]; //cout << "dis[i] = " << dis[i] << endl; } //cout << "maxdis = " << maxdis << endl; int left = 1, right = maxdis, mid = (left + right) / 2; while (left < right) { //cout << "mid = " << mid << endl; if (Validate(mid)) { if (left == mid) { break; } left = mid; } else { right = mid - 1; } mid = (left + right) / 2; } cout << mid << endl; return 0; }