Minimum-Cost Expedition Landing
Autumn Tournament (2022)
Submission name: expedition.cpp
Problem summary
Each expedition starts at the road’s origin, must land once at a listed helicopter pad, then walks in either direction to its destination. Pad i costs B[i] to reach and is at coordinate A[i]; walking costs C per unit distance. Find the minimum total cost for every destination.
Input
N M C; N pairs A[i] B[i] for distinct pad coordinates; then M destination coordinates.
Output
One minimum cost per destination, in input order.
Constraints
1 ≤ N,M ≤100000; 1 ≤ C ≤1000000000; 0 ≤ A[i],B[i],D[j] ≤1000000000.
Worked example
Original statement sample.
Input
3 2 1 200 300 300 100 100 250 150 110
Output
250 260
Solution analysis
- The cost through a pad at A is B+C·|D−A|. Sort pads by A. For pads left of D, rewrite the cost as C·D+(B−C·A). For pads right of D, rewrite it as−C·D+(B+C·A).
- Precompute prefix minima of B−C·A and suffix minima of B+C·A. Binary-search the first pad whose coordinate is at least D. The prefix before it supplies the best left landing; the suffix from it supplies the best right landing. Take the smaller available candidate.
- For D=150 in the sample, landing at 300 costs 100+150=250, while landing at 100 costs 250+50=300. For D=110, the pad at 100 costs 250+10=260 and wins. The geographically nearest pad need not minimize the full cost because flight charges differ.
Why it works
The absolute-value formula splits the pads into two exhaustive coordinate ranges. Within either range, the destination-dependent term is the same for every pad, leaving precisely the stored prefix or suffix minimum. Comparing these two minima therefore considers the best choice over all possible landings.
Watch out. Landing is mandatory even when the destination is 0 or coincides with the origin. Do not choose a pad by distance alone. Use long long: C·A and C·D can approach 10^18.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<limits>
#include<utility>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
int queries;
long long walkingCost;
cin>>n>>queries>>walkingCost;
vector<pair<long long,long long>>pads(n);
for(auto&pad:pads){
cin>>pad.first>>pad.second;
}
sort(pads.begin(),pads.end());
vector<long long>coordinates(n);
vector<long long>prefix(n);
vector<long long>suffix(n);
// Separate the absolute value into left and right landing formulas.
for(int i=0;i<n;i++){
coordinates[i]=pads[i].first;
long long cost=pads[i].second-walkingCost*coordinates[i];
prefix[i]=i==0?cost:min(prefix[i-1],cost);
}
for(int i=n-1;i>=0;i--){
long long cost=pads[i].second+walkingCost*coordinates[i];
suffix[i]=i==n-1?cost:min(suffix[i+1],cost);
}
while(queries--){
long long destination;
cin>>destination;
int firstRight=static_cast<int>(
lower_bound(coordinates.begin(),coordinates.end(),destination)-coordinates.begin());
long long answer=numeric_limits<long long>::max();
if(firstRight>0){
answer=min(answer,walkingCost*destination+prefix[firstRight-1]);
}
if(firstRight<n){
answer=min(answer,suffix[firstRight]-walkingCost*destination);
}
cout<<answer<<'\n';
}
}