In this HackerEarth Destination cost problem solution You are given N destinations that must be covered in N days in any order. Any ith (1 <= i <= N) destination can be traveled on any jth (1 <= j <= N) day. There are only two ways to reach any destination and that is by cars or buses. The cost of reaching to the ith destination by cars (C1,C2,.....Cn) and buses (B1,B2,....Bn) are given.

The only constraint is that you cannot use the same way of travel on two consecutive days. Determine the minimum total cost that you need to pay in reaching all N destinations.


HackerEarth Destination cost problem solution


HackerEarth Destination cost problem solution.

#include<bits/stdc++.h>
using namespace std;

int main()
{
int n;
cin>>n;
int c[n],b[n];
for(int i=0;i<n;i++)
{
cin>>c[i];
}
for(int i=0;i<n;i++)
{
cin>>b[i];
}
long long ans=0;
vector<int> bus,car;
for(int i=0;i<n;i++)
{
if(b[i]<c[i])
{
ans+=b[i];
bus.push_back(c[i]-b[i]);
}
else
{
ans+=c[i];
car.push_back(b[i]-c[i]);
}
}
int bus_sz=bus.size(),car_sz=car.size();
if(abs(bus_sz-car_sz)<=1)
{
cout<<ans<<endl;
}
else
{
int r=abs(bus_sz-car_sz)/2;
if(bus_sz>car_sz)
{
sort(bus.begin(),bus.end());
for(int i=0;i<r;i++)
{
ans+=bus[i];
}
}
else
{
sort(car.begin(),car.end());
for(int i=0;i<r;i++)
{
ans+=car[i];
}
}
cout<<ans<<endl;
}
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e5 + 14;
int n, b[maxn], c[maxn], per[maxn];
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++)
cin >> b[i];
for(int i = 0; i < n; i++)
cin >> c[i];
iota(per, per + n, 0);
sort(per, per + n, [](int i, int j){ return b[i] - c[i] < b[j] - c[j]; });
ll ans = 0;
for(int i = 0; i < n; i++)
if(i < n / 2)
ans += b[ per[i] ];
else if(i >= (n + 1) / 2)
ans += c[ per[i] ];
else
ans += min(b[ per[i] ], c[ per[i] ]);
cout << ans << '\n';
}