Maximum Computer Profit
Autumn Tournament (2011)
Submission name: profit.cpp
Problem summary
A company has n processor units and m monitors. Pairing a processor of value a with a monitor of value b produces a computer worth a·b. Each component can be used once. Build as many computers as possible and maximize their total value.
Input
n m, then n processor values, then m monitor values.
Output
The maximum number of computers and the maximum total value.
Constraints
1 ≤ n, m ≤ 1000; component values are integers from 1 to 1000.
Worked example
Original statement sample, with whitespace restored where PDF extraction merges adjacent numbers.
Input
4 2 1 2 3 4 5 6
Output
2 39
Solution analysis
- The maximum number of computers is k=min(n,m). All values are positive, so from either surplus component list we should keep its k largest values: replacing a chosen value with a larger unused one cannot hurt.
- Sort both lists in descending order and pair corresponding positions. Pairing large with large is optimal. For a≥b and c≥d, the difference between aligned and crossed pairings is ac+bd-ad-bc=(a-b)(c-d)≥0.
- In the sample, use processors 4 and 3 with monitors 6 and 5. Their total is 4·6+3·5=39. Using processor 1 or 2 would waste one of the two available monitor slots.
Why it works
An exchange replaces any omitted larger component without decreasing value. Once the largest k components are chosen on each side, repeatedly undoing inverted pairs using the nonnegative exchange difference yields sorted matching, proving its optimality.
Watch out. Maximize the number of pairs before their value. Do not pair largest with smallest. Use an integer total; long long safely accommodates all products and sums.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n;
int m;
cin>>n>>m;
vector<int>processors(n);
vector<int>monitors(m);
for(int&value:processors){
cin>>value;
}
for(int&value:monitors){
cin>>value;
}
sort(processors.rbegin(),processors.rend());
sort(monitors.rbegin(),monitors.rend());
int computers=min(n,m);
long long total=0;
// Sorted pairing maximizes the sum of products.
for(int i=0;i<computers;++i){
total+=1LL*processors[i]*monitors[i];
}
cout<<computers<<' '<<total<<'\n';
}