UVa 907

907 - Winterim Backpacking Trip

http://uva.onlinejudge.org/external/9/907.html

Summary

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.

Explanation

Use binary search to "guess" the minimum of maximum distance. If the number of camp is less than or egual to K, keep lowering the maximum distance needed. Otherwise, increase it.

Implementations

#define INF 2000000000
#define FOR(i,a,n) for(int i=a,_n=n; i<_n; i++)
 
int N, K;
int arr[605], pos[605];
 
//Check whether the number x you guess satisfy the number of maximum camping needed
 
bool check(int x){
     int y = x, camp = 0;
     FOR (i, 0, N+1){
         int dif = pos[i+1] - pos[i];
         if ( y >= dif ) y -= dif;
         else{
              camp++;
              y = x-dif;              
         }    
         if ( camp > K || y < 0 ) return false;
     }     
     return true;
}
 
//Main 
 
int main(){
    while ( scanf("%d %d", &N, &K) == 2 ){
          FOR (i, 1, N+2) scanf("%d", &arr[i]);
 
          pos[0] = 0;
          FOR (i, 1, N+2) pos[i] = arr[i] + pos[i-1];       
 
          int left = pos[0], right = pos[N+1];
          int dist = INF;
 
          while ( left <= right ){
                int mid = ((LL)left+right)/2;
                if ( check(mid) ) dist = min(dist, mid), right = mid-1;
                else left = mid+1;
          }
 
          printf("%d\n", dist);
    }
    return 0;
}

Input

4 1
7
2
6
4
5
4 2
7
2
6
4
5
4 3
7
2
6
4
5
4 10
7
2
6
4
5

Output

15
9
8
7