时间限制 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;
}