Discount Bus Passes
National Olympiad — Regional round (2012 season)
Submission name: bus.cpp
Problem summary
Travel from stop A to B on an ordered line. Each adjacent-stop ticket costs 1. A pass of price c covers any portion of its inclusive stop interval [l,r]. Buy any combination of passes and tickets to minimize the cost.
Input
N A B, followed by N triples l r c.
Output
The minimum travel cost.
Constraints
At most 1000000 stops; A<B; 1≤N≤10000; each pass costs less than r−l.
Worked example
An independently prepared example for this explanation.
Input
4 7 34 18 35 5 10 14 2 5 16 10 10 37 20
Output
14
Solution analysis
- Clamp every pass to the journey interval [A,B] and discard passes that cover no positive distance. Only A, B and pass endpoints are needed as coordinates; between consecutive endpoints, ordinary tickets cost their coordinate difference.
- Process these coordinates from left to right. A pass starting at l creates an offer of cost best[l]+c, valid through r. Maintain offers in a minimum heap by total cost, lazily removing those whose r lies before the current coordinate. The current best cost is the smaller of an active offer and the previous best plus the ticket gap.
- The sample buys three tickets from 7 to 10, the 10–14 pass for 2, four tickets to 18 and the 18–35 pass for 5, stopping at 34. The total is 3+2+4+5=14. A pass can be used for only part of its range.
Why it works
The optimal cost to reach positions along a line is nondecreasing: truncate any covering journey to obtain a covering journey to an earlier position. Hence, among all possible entry points into a pass, its earliest available point l has minimum preceding cost. Every optimum therefore ends with ordinary tickets or a pass offered at its clamped left endpoint. The sweep evaluates both cases and maintains their exact minimum.
Watch out. Passes extending beyond A or B remain usable. Overlapping passes are allowed. Expire a pass only after its right endpoint.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<functional>
#include<utility>
using namespace std;
struct Pass{
int left;
int right;
int cost;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int count,start,finish;
cin>>count>>start>>finish;
vector<Pass>passes;
vector<int>positions={start,finish};
for(int i=0;i<count;i++){
int left,right,cost;
cin>>left>>right>>cost;
left=max(left,start);
right=min(right,finish);
if(left<right){
passes.push_back({left,right,cost});
positions.push_back(left);
positions.push_back(right);
}
}
sort(positions.begin(),positions.end());
positions.erase(unique(positions.begin(),positions.end()),positions.end());
sort(passes.begin(),passes.end(),[](const Pass&a,const Pass&b){
return a.left<b.left;
});
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>offers;
long long best=0;
int previous=start;
size_t nextPass=0;
for(int position:positions){
best+=position-previous;
while(!offers.empty()&&offers.top().second<position){
offers.pop();
}
if(!offers.empty()){
best=min(best,offers.top().first);
}
// A newly starting pass is useful only for subsequent positions.
while(nextPass<passes.size()&&passes[nextPass].left==position){
offers.push({best+passes[nextPass].cost,passes[nextPass].right});
nextPass++;
}
previous=position;
}
cout<<best<<'\n';
}