Lightoj 1048 - Conquering Keokradong

Problem link:

Problem Analysis:

It is actually a basic Bisection problem , as we can see here we can not actually find a formula for the camp distance but what we can do is for a certain camp distance we can check how many nights or how many nights we must stay in a camp. and if that's less than k than we are good but else we need to check for smaller distances.

 here isp() function just validates for any certain distance is it possible to do it less than or equal k nights or not. and in the main function that bisection just puts the data from the function to Isp() to search for a better result.

If for certain "l" Isp(l) returns true than we check if there is another l' which is l'<l and still isp(l')  returns true or not.

else we increse I and check for the isp(I) for which it is true result again. The printing part is a little tricky But can be done. 

Here goes the code:  

1. #include <bits/stdc++.h>
2. using namespace std;
3. vector<int>v;
4. int k;
5. bool isp(int l){
6.     int co = 0;
7.     int sum =v[0];
8.     for(int i = 1; i <v.size(); i++){
9.         if(v[i]>l) return false;
10.         else if(sum+v[i]<=l){
11.             sum+= v[i];
12.         }
13.         else{
14.             sum = v[i];
15.             co++;
16.         }
17.     }
18.     if(co<=k) return true;
19.     return false;
20. }
21. void prt(int l){
22.     int sum= 0;
23.     int co = 0;
24.     for(int i = 0; i <v.size(); i++){
25.         sum+= v[i];
26.         if(sum>l){
27.             printf("%d\n", sum-v[i]);
28.             sum = v[i];
29.             co++;
30.         }
31.         if(k-co+1>=v.size()-i){
32.             printf("%d\n", sum);
33.             for(int j = i+1; j <v.size(); j++) printf("%d\n", v[j]);
34.             break;
35.         }
36.     }
37. }
38. int main(){
39.     int ts;
40.     scanf("%d", &ts);
41.     for(int p = 1; p <= ts; p++){
42.     v.clear();
43.     int n,low = INT_MIN, high = 0, mid = 0, ans;
44.     scanf("%d%d", &n, &k);
45.     for(int i = 0; i <=n; i++){
46.         int a;
47.         scanf("%d", &a);
48.         high+= a;
49.         v.push_back(a);
50.         low = max(low, a);
51.     }
52.     while(high-low>2){
53.         mid = (low+high)/2;
54.         if(isp(mid)) high = mid;
55.         else low = mid;
56.     }
57.     for(int i  = high; i >= low; i--) if(isp(i)) ans = i;
58.     printf("Case %d: %d\n",p,  ans);
59.     prt(ans);
60.     }
61.     return 0;
62. }