Разбор

Рассмотрим случай массивов с двумя элементами. Пусть $A=\{p,q\}(p<q),B=\{x,y\}$. Рассмотрим условие, при котором сумма $p\cdot x+q\cdot y$ будет наименьшей. Рассмотрим два варианта перестановок:

Неравенство $p\cdot x+q\cdot y<p\cdot y+q\cdot x$ имеет место, если

Учитывая что $p\ne q$, разделим неравенство на $(p-q)<0$. Получим $x>y$.

То есть сумма $p\cdot x+q\cdot y$ (при $p<q$) будет минимальной, если $x>y$.

Рассмотрим пару элементов исходных массивов $A$ и $B$. Если $a_i<a_j,b_i<b_j$, то поменяв местами $b_i$ и $b_j$, мы уменьшим общую сумму.

Отсортируем массив $a$ по возрастанию, а массив $b$ по убыванию. Тогда получим сумму с наименьшим значением

Пример

Вычислим сумму для данных из примера.

Возьмем пару для которой $a_1<a_5$ и $b_1<b_5$. Поменяем местами $b_1$ и $b_5$. Сумма уменьшится.

Для заданного примера для любой пары $(i,j)$ выполняется: если $a_i<a_j$, то $b_i>b_j$. Следовательно текущая перестановка оптимальная.

Рассмотрим получение минимальной суммы, отсортировав $a$ по возрастанию, а массив $b$ по убыванию.

Реализация алгоритма

Объявим входные массивы чисел.

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

Читаем входные данные.

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

Сортируем первый массив по возрастанию, второй — по убыванию.

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

Вычисляем искомую минимальную сумму, значение которой может быть $64$-битовым целым.

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

Выводим результат.

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

Java реализация

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();
  }
}   

Python реализация

Читаем входные данные.

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

Сортируем первый массив по возрастанию, второй — по убыванию.

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

Вычисляем искомую минимальную сумму.

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

Выводим результат.

print(res)