Honey Exhibition
Autumn Tournament (2013)
Submission name: honey.cpp
Problem summary
Three kinds of honey have prices A1, A2 and A3 per kilogram. Three containers hold B1, B2 and B3 kilograms. Fill every container with one different kind of honey, without mixing, to maximize total sales revenue.
Input
Three prices on the first line; three container capacities on the second line.
Output
The maximum total revenue.
Constraints
0 < A1, A2, A3, B1, B2, B3 ≤ 100,000,000.
Worked example
Original statement sample, translated without changing its numeric data.
Input
7 2 9 10 5 3
Output
131
Solution analysis
- Sort the prices and capacities into increasing order. Pair the smallest price with the smallest container, the middle with the middle, and the largest with the largest.
- For prices x ≤ y and capacities u ≤ v, the paired total xu + yv exceeds or equals the crossed total xv + yu by (y − x)(v − u), which is nonnegative. So exchanging a mismatched pair cannot hurt revenue.
- The sample sorts to prices 2, 7, 9 and capacities 3, 5, 10. Their paired products sum to 6 + 35 + 90 = 131. Use long long: the total can reach 30,000,000,000,000,000.
Why it works
If a pairing assigns a lower price to a larger container than a higher price, swapping those two assignments changes revenue by a nonnegative product of their differences. Repeatedly remove such inversions until prices and capacities are paired in the same order. Revenue never decreases, so the sorted pairing is optimal.
Watch out. A product can reach 10^16, so both input arrays and the total must use long long. Equal prices or capacities do not affect the argument.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
long long prices[3],capacities[3];
for(long long&price:prices){
cin>>price;
}
for(long long&capacity:capacities){
cin>>capacity;
}
sort(prices,prices+3);
sort(capacities,capacities+3);
long long revenue=0;
for(int i=0;i<3;i++){
// Match expensive honey to a larger container.
revenue+=prices[i]*capacities[i];
}
cout<<revenue<<'\n';
}