Greedy Algorithms with Sorting

Sorting often turns a global optimization into a sequence of local assignments, but the correct direction depends on the objective. This lesson minimizes a scalar product by pairing two freely reorderable arrays in opposite sorted orders. It illustrates how an algebraic exchange chooses ascending versus descending processing, rather than guessing that smaller is always better.

Prerequisites: Sorting comparators; exchange arguments; algebraic inequalities.

Build the idea

1. Model the available choices

   There are n coefficients ai and n multipliers bj, and every element must be used exactly once in a pairing. The total is the sum of the products of paired values. There are no compatibility restrictions between pairs. Sort a descending and b ascending, then pair equal indices. The code reports the minimum cost, not original pair IDs; reconstructing IDs would require storing them with the values.

2. Compare two assignments

   Let A≥a and B≥b. Pairing large with large costs AB+ab; crossing the pairs costs Ab+aB. Their difference is (A−a)(B−b), which is nonnegative. Therefore putting larger a with smaller b cannot be worse. This inequality is the reason for opposite sorting orders; the sort itself is not the proof.

   $$\mathrm{AB}+\mathrm{ab}-\mathrm{Ab}-\mathrm{aB}=(A-a)(B-b)\ge 0$$

3. Correctness proof: eliminate inversions

   Fix a in descending order. If the assigned b sequence contains an inversion B before b, swap those two assignments. Feasibility is unchanged because every pairing is allowed, and the two-product inequality does not increase cost. Repeated swaps produce ascending b, so an optimum exists in the greedy order. The reasoning also identifies same-order pairing as a maximization rule for the corresponding unconstrained scalar product.

4. Trace the sample

   Arrays a=[1,3,2],b=[4,1,2] become [3,2,1] and [1,2,4]. Contributions are 3,4,4 for total 11. Sorting both ascending instead gives 1+4+12=17, the opposite effect. Equal values can be interchanged freely without changing the objective. Zero values are legal and naturally pair according to the same inequality.

5. Recognize sorting’s limits

   Sorting discards original position information, so it is invalid if the problem demands order preservation or restricts which elements can match. A multi-resource constraint may require matching or flow instead. This program uses nonnegative values up to 10^6 to give a transparent overflow bound, although the algebraic rearrangement inequality itself is more general. Always separate the mathematical statement from the implementation’s numeric contract.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
int main(){
    int n;
    std::cin>>n;
    std::vector<long long>a(n),b(n);
    for(auto&x:a){
        std::cin>>x;
    }
    for(auto&x:b){
        std::cin>>x;
    }
    std::sort(a.begin(),a.end(),std::greater<long long>());
    std::sort(b.begin(),b.end());
    long long total=0;
    for(int i=0;i<n;++i){
        total+=a[i]*b[i]; // Opposite orders minimize the scalar product.
    }
    std::cout<<total<<'\n';
}

Complexity analysis

O(n log n) time for two sorts and O(n) for products; O(n) storage. Each product is at most 10^12 and the sum at most 10^17, so long long is sufficient under these bounds.

Example input and output

Read n (0..100000), then array a and array b of n integers in 0..10^6. Arbitrary one-to-one pairings are allowed. Print the minimum sum of pairwise products.

Input

3
1 3 2
4 1 2

Output

11

Pair 3 with 1, 2 with 2, and 1 with 4, producing 3+4+4.

Practical applications

Use exchange inequalities to derive ordering rules for unrestricted assignments and scheduling costs. If the algebra gives no consistent pairwise order, a simple sorting rule may not exist. Interval problems sort by finishes or starts for entirely different reasons.

Check your understanding

Which fact justifies opposite sorting orders?

Put it into practice

Compare all multiplier permutations for arrays of length four.