#include "ricehub.h"
#include <iostream>
// #include <map>
#include <vector>
#include <algorithm>
using namespace std;
int besthub(int R, int L, int X[], long long B) // this is my ricehub implementation for now
//will come back later to try and improve it;
{
// return R;
// kind of like the binary search on answer, check which place when the hub is placed will
// give us a total transport cost <=B(baht)
// so here taking the answer on which I am binary searching to be the position to place the hub
// so starting from the middle then I compute the total cost to place it those places
// total cost is the absolute value of the distance between a hub and our rice hub
// long long lb = 0;
// long long rb = L;
// long long mid = lb + (rb-lb)/2;
vector<long long> window = {0,1};
long long sum_of_dist_to_hub = 0;
long long median;
while (window[1]<= R-1){
sum_of_dist_to_hub = 0;
for(long long i=window[0];i<R+1; i++){
if(sum_of_dist_to_hub>B && window[0]<R){
window[0] = 1;
continue;
}
median = (window[0] + window[1])/2;
sum_of_dist_to_hub+=abs(X[i] - median);
}
if(sum_of_dist_to_hub<B){
window[1] = window[1]+1;
}
}
long long ans = window[1] - window[0];
cout<< ans << endl<< "Hubs are between " << window[0] << "and " << window[1];
return ans;
}
