#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;
long long sum_of_dist_to_hub = 0;
long long median;
long long left = 0;
long long max_truckloads = 0;
for(long long right = 0; right<R;right++){
sum_of_dist_to_hub = 0;
long long median_index = (left+right)/2;
for(long long i=left;i<=right;i++){
sum_of_dist_to_hub+= abs(X[i] - X[median_index]);
}
while (sum_of_dist_to_hub>B && left<R){
sum_of_dist_to_hub = 0;
left++;
long long median_index = (left+right)/2;
for(long long i=left;i<=right;i++){
sum_of_dist_to_hub+= abs(X[i] - X[median_index]);
}
}
max_truckloads = max(max_truckloads, (right-left+1)); // cause it is 0 indexed [1,2,4] will be left =0 right = 2 2-0 = 2 but there are actually 3 items so +1;
}
// cout<< max_truckloads << endl;
return max_truckloads;
}
