In this HackerEarth Customer satisfaction problem solution Alice is the biggest seller in the town who sells notebooks. She has N customers to satisfy. Each customer has three parameters Li, Ri, and Zi denoting the arrival time, departure time, and quantity of notebooks required.
Each customer has to be supplied a total of Zi notebooks between Li and Ri inclusive. What is the minimum rate of W notebooks per unit time by which if Alice produces so that it satisfies the demand of each customer?
Note that Alice does not need to supply Zi to customer i for per unit time but the total of Zi between Li and Ri and distribution does not need to be uniform.
HackerEarth Customer satisfaction problem solution.
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define endl "\n"
#define test ll t; cin>>t; while(t--)
typedef long long int ll;
bool check(vector<pair<ll,ll>>&vp,ll n,ll quan){
ll ok=true;
ll ans=vp[0].first*quan;
for(ll i=0;i<n;i++){
if(i>0){
ans+=(vp[i].first-vp[i-1].first)*quan;
}
if(ans<vp[i].second){
ok=false;
}
ans-=vp[i].second;
}
return ok;
}
int main() {
FIO;
test
{
ll n,l,r,w; cin>>n;
vector<pair<ll,ll>>vp;
for(int i=0;i<n;i++){
cin>>l>>r>>w;
vp.push_back({r,w});
}
sort(vp.begin(),vp.end());
for(auto it:vp){
cout<<it.first<<" "<<it.second<<endl;
}
ll st=0,dr=1e18,ans,mid;
while(st<=dr){
mid=(st+dr)/2;
if(check(vp,n,mid)){
ans=mid;
dr=mid-1;
}
else{
st=mid+1;
}
}
cout<<ans<<endl;
}
return 0;
}
Second solution
MAX = 10000
t = int(input())
while t > 0:
t -= 1
n = int(input())
need = {}
for i in range(n):
[l, r, z] = map(int, input().split())
if r not in need:
need[r] = 0
need[r] += z
ans = 0
li = list(need.items())
li.sort()
cur_need = 0
for key, val in li:
cur_need += val
ans = max(ans, (cur_need + key - 1) // key)
print(ans)
0 Comments