algorithm - How to find the minimum value of M? -
i'm trying solve problem:
you have n relatives. talk ith relative ti minutes. each minute costs 1 dollar . after conversation, add recharge of xi dollars in mobile. initially, have m dollars balance in mobile phone.
find minimum value of m, must have initially, in phone, don't run out of balance during of call (encounter negative balance).
note : can call relatives in order. each relative called once.
input:
n t1 x1 t2 x2 2 1 1 2 1
output:
2
this looks easy me @ first i'm not able find exact solution.
my initial thoughts:
we have no problem
xi > ti
not reduce our initial balance. need take care of situation where run loss i.eti > xi
. unable make expression result in minimum initial value.
need guidance in approaching problem find optimal solution.
update:-
binary search approach seems lead wrong result (as proved test case provided in comment below user greybeard.
so, approach.we maintain difference between call cost , recharge amount.
then maintain 2 arrays/vectors. if our recharge amount strictly greater cost of call, put call in first array ,else put in second array.
then can sort first array according cost , second array according recharge amount. update diff adding least amount of recharge call our cost greater recharge
then can iterate through our first array , update our max requirement,requirement each call , current balance.finally, our answer maximum between max requirement , diff have maintained.
example :-
n = 2 t1 = 1 r1 = 1 t2 = 2 r2 = 1
our first array contains nothing calls have cost greater or equal recharge amount. so, place both calls in our second array diff gets updated 2 before sort array. then, add min recharge can calls our diff(i.e 1).now, diff stands @ 3.then our first array contains no elements, our answer equal diff i.e 3.
time complexity :- o(nlogn)
working example:-
#include<bits/stdc++.h> using namespace std; #define maxn 100007 int n,diff; vector<pair<int,int> > v1,v2; int main(){ diff = 0; cin>>n; for(int i=0;i<n;i++){ int cost,recharge; cin>>cost>>recharge; if(recharge > cost){ v1.push_back(make_pair(cost,recharge)); }else{ v2.push_back(make_pair(recharge,cost)); } diff += (cost-recharge); } sort(v1.begin(), v1.end()); sort(v2.begin(), v2.end()); if(v2.size() > 0)diff += v2[0].first; int max_req = diff, req = 0,cur = 0; for(int i=0; i<v1.size(); i++){ req = v1[i].first - cur; max_req = max(max_req, req); cur += v1[i].second-v1[i].first; } cout<<max(max_req,diff)<<endl; return 0; }
Comments
Post a Comment