Redaksiya
Consider the case of arrays with two elements. Let and . Let's examine the condition under which the sum will be minimized. Let's consider two permutation options:
The inequality holds if
Given that , dividing the inequality by , we obtain . This means that the sum (when ) will be minimized if .
Consider a pair of elements from the original arrays and . If and , then by swapping and , we decrease the total sum.
Sort array in ascending order and array in descending order. Then we'll obtain the sum with the smallest value
Example
Compute the sum for the given example.
Let's take a pair where and . Swapping and will decrease the sum.
For the given example, for any pair , if , then . Therefore, the current permutation is optimal.
Let’s consider obtaining the minimum sum by sorting array in ascending order and array 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 -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(); } }
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)