Carry All Buckets in Fewest Trips
National Olympiad — National round (2010 season)
Submission name: water.cpp
Problem summary
Carry full buckets with at most two buckets and k litres per trip. Contents cannot be split. Find the minimum trips.
Input
n k, then n bucket volumes.
Output
The fewest trips.
Constraints
1 ≤ n ≤100000;1 ≤ k ≤10^9; each volume is positive and at most k.
Worked example
Input and output for the worked example discussed below.
Input
6 9 5 9 7 8 4 3
Output
5
Solution analysis
- Sort volumes and consider the heaviest remaining bucket. If it cannot share with the lightest, it cannot share with any bucket, so its solo trip is forced.
- Otherwise pair the extremes. If an optimal arrangement used partners x for the heaviest and y for the lightest, pairing the extremes leaves x+y feasible because y≤heaviest and x+heaviest already fit. Cases involving singles need no extra trip.
- Remove the heaviest every trip and the lightest only when paired. The sample permits only one pair in an optimum, so four singleton trips plus that pair give5 trips.
Why it works
The solo case is unavoidable. The exchange argument makes the feasible extreme pair part of an optimal arrangement without adding trips. Removing that trip leaves the same problem on fewer buckets, proving the greedy algorithm by induction.
Watch out. At most two buckets may travel together. Never split water and remember a final singleton.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long capacity;
cin>>n>>capacity;
vector<long long>buckets(n);
for(long long&volume:buckets){
cin>>volume;
}
sort(buckets.begin(),buckets.end());
int left=0;
int right=n-1;
int trips=0;
while(left<=right){
// If the lightest does not fit, the heaviest must travel alone.
if(left<right&&buckets[left]+buckets[right]<=capacity){
left++;
}
right--;
trips++;
}
cout<<trips<<'\n';
}