Given the distances between N consecutive campsites of a trail and given the number of nights for your trip, K, your task is to devise a camping strategy for the specified trail such that it minimises the maximum amount of walking done in a single day. Note that the first distance value given is the distance from our start-point of the trail to our 1st campsite, and the last distance value given is the distance from our Nth campsite to our end-point of the trail.

Input

The input file contains several test cases, each of them as describes below.
The first line of input consists of two numbers, the number of campsites (0 < N <= 600) and the number of nights of the trip (0 <= K <= 300). The following N+1 input lines indicate the distance in miles between consecutive campsite locations.

Output

4 3
7
2
6
4
5

8

這題的另外一個方法是 DP，效率 O(N*N*K)

那麼使用二分搜答案，使用 O(n) 去驗證，效率 O(N*log(ans))




#include <stdio.h>
int A[605], n, m;
int check(int res) {
    int sum = 0, cnt = 0, i;
    for(i = 0; i <= n; i++) {
        if(A[i] > res)  return 0;
        if(sum+A[i] > res)
            sum = A[i], cnt++;
        else
            sum += A[i];
    }
    if(sum) cnt++;
    return cnt <= m;
}
int main() {
    int i;
    while(scanf("%d %d", &n, &m) == 2) {
        n++, m++;
        for(i = 0; i < n; i++)
            scanf("%d", &A[i]);
        int l = 0, r = 1000000, mid;
        while(l <= r) {
            mid = (l+r)/2;
            if(check(mid))
                r = mid-1;
            else
                l = mid+1;
        }
        printf("%d\n", r+1);
    }
    return 0;
}