Minimum Sum#6198

Minimum Sum (Editorial)

Consider the case of arrays with two elements. Let $A = {p, q} (p < q)$ A = \{p, q\}~(p < q) and $B = {x, y}$ B = \{x, y\}. Let's examine the condition under which the sum $p \cdot x + q \cdot y$ p \cdot x + q \cdot y will be minimized. Let's consider two permutation options:

The inequality $p \cdot x + q \cdot y < p \cdot y + q \cdot x$ p \cdot x + q \cdot y < p \cdot y + q \cdot x holds if

x \cdot (p - q) < y \cdot (p - q)

x \cdot (p - q) < y \cdot (p - q)

Given that $p \neq = q$ p \ne q, dividing the inequality by $(p - q) < 0$ (p - q) < 0, we obtain $x > y$ x > y. This means that the sum $p \cdot x + q \cdot y$ p \cdot x + q \cdot y (when $p < q$ p < q) will be minimized if $x > y$ x > y.

Consider a pair of elements from the original arrays $A$ and $B$ . If $a_{i} < a_{j}$ a_i < a_j and $b_{i} < b_{j}$ b_i < b_j, then by swapping $b_{i}$ b_i and $b_{j}$ b_j, we decrease the total sum.

Sort array $a$ in ascending order and array $b$ in descending order. Then we'll obtain the sum with the smallest value

i = 1 \sum n a_{i} \cdot b_{i}

\sum_{i=1}^n a_i \cdot b_i

Example

Compute the sum for the given example.

Let's take a pair where $a_{1} < a_{5}$ a_1 < a_5 and $b_{1} < b_{5}$ b_1 < b_5. Swapping $b_{1}$ b_1 and $b_{5}$ b_5 will decrease the sum.

For the given example, for any pair $(i, j)$ , if $a_{i} < a_{j}$ a_i < a_j, then $b_{i} > b_{j}$ b_i > b_j. Therefore, the current permutation is optimal.

Let’s consider obtaining the minimum sum by sorting array $a$ in ascending order and array $b$ in descending order.

Algorithm realization

Declare the input arrays.

#define MAX 101
int a[MAX], b[MAX];

Read the input data.

scanf("%d",&n);
for(i = 0; i < n; i++)
  scanf("%d",&a[i]);
for(i = 0; i < n; i++)
  scanf("%d",&b[i]);

Sort the first array in ascending order, and the second array in descending order.

sort(a,a+n);
sort(b,b+n,greater<int>());

Compute the desired minimum sum, which can be a $64$ -bit integer.

res = 0;
for(i = 0; i < n; i++)
  res += 1LL * a[i] * b[i];

Print the answer.

printf("%lld\n",res);

Java realization

import java.util.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    Integer a[] = new Integer[n];
    for(int i = 0; i < n; i++)
      a[i] = con.nextInt();
    
    Integer b[] = new Integer[n];
    for(int i = 0; i < n; i++)
      b[i] = con.nextInt();
    
    Arrays.sort(a);
    Arrays.sort(b,Collections.reverseOrder());
    
    long res = 0;
    for(int i = 0; i < n; i++)
      res += 1L * a[i] * b[i];
    
    System.out.println(res);
    con.close();
  }
}

Java

Python realization

Read the input data.

n = int(input())
l1 = list(map(int,input().split()))
l2 = list(map(int,input().split()))

Sort the first array in ascending order, and the second array in descending order.

l1.sort()
l2.sort(reverse = True)

Compute the desired minimum sum.

res = 0
for i in range(n):
  res += l1[i] * l2[i]

Print the answer.

print(res)