时间限制 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<stdio.h>
#include<math.h>
#include <iostream>
using namespace std;
bool binarySearch(int mid, int b[], int m, int n);
int main(){
int m, n;
int *a,*b;
cin >> n >> m;
a = (int *)malloc(sizeof(int) * (n+1)); // 分配
b = (int *)malloc(sizeof(int) * (n+1 )); // 分配
for (int i = 0; i<n + 1; i++)
{
a[i] = b[i] = 0;
}
for (int i = 2; i<n + 1; i++)
{
cin >> a[i]; // 键盘输入 n-1 个数
b[i] = a[i] + b[i - 1];
}
int left = 0, right = b[n], mid;
while (left<right-1){
mid = (left + right) / 2;
if (binarySearch(mid, b, m, n) == false){
left = mid;
}
else{
right = mid;
}
}
cout << left << endl;
return 0;
}
bool binarySearch(int mid ,int b[],int m,int n){
int count = 0, sum = 0, j = 1;
for (int i = 2; i < n + 1;) {
int dis = b[i] - b[j];
while (dis < mid){
count++;
i++;
if (count > m){
return true;
}
if (i > n){
if (j == 1){
return true;
}
else{
return false;
}
}
dis = b[i] - b[j];
}
j = i;
i++;
}
return false;
}
