➤ Problem Link : KOPC12A
👉 Hint : edit please
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll cost[10001];
ll arr[10001];
ll n;
ll Func(ll m)
{
ll ans=0;
for(ll i=0;i<n;i++)
ans+=(abs(m-arr[i])*cost[i]);
return ans;
}
ll Ternary_search(ll l,ll r)
{
ll m1;
ll m2;
ll ans=LONG_MAX;
while(r-l>2)
{
m1=(2*l+r)/3;
m2=(l+2*r)/3;
if(Func(m1)<Func(m2))
r=m2;
else if(Func(m1)==Func(m2))
{
l=m1,r=m2;
}
else
l=m1;
}
for(ll i=l;i<=r;i++)
ans=min(ans,Func(i));
return ans;
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n;
for(ll i=0;i<n;i++)
cin>>arr[i];
for(ll i=0;i<n;i++)
cin>>cost[i];
cout<<Ternary_search(0,INT_MAX)<<endl;
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.