재배열 부등식(rearrangement inequality)을 이용한 내적의 최대 최소

1. 재배열 부등식(rearrangement inequality)

 

실수 $x_{1} <= x_{2} <=  ...  <= x_{n}$과 $y_{1} <= y_{2} <= ... <= y_{n}$에 대하여

 

1,2,..,n의 임의의 순열 $\sigma_{1}, \sigma_{2}, ... , \sigma_{n}$으로부터

 

$$x_{1}y_{n} + x_{2}y_{n-1} + ... + x_{n}y_{1} <= x_{1}y_{\sigma_{1}} + x_{2}y_{\sigma_{2}} + ... + x_{n}y_{\sigma_{n}} <= x_{1}y_{1} + x_{2}y_{2} + ... +x_{n}y_{n}$$

 

 

2. 증명

 

$S1 = x_{1}y_{1} + x_{2}y_{2} + .... + x_{a}y_{a} + .... + x_{b}y_{b} + ... + x_{n}y_{n}$에서 $y_{a} <= y_{b}$를 서로 바꾸면

 

$S2 = x_{1}y_{1} + x_{2}y_{2} + ... + x_{a}y_{b} + ... + x_{b}y_{a} + ... + x_{n}y_{n}$

 

둘을 뺴면 $S1 - S2 = x_{a}(y_{a} - y_{b}) + x_{b}(y_{b} - y_{a}) = (x_{a} - x_{b})(y_{a} - y_{b}) >= 0$

 

따라서 S1 >= S2인데, Y에서 임의의 두 항을 바꾸면 S1에서 값이 반드시 작아진다.

 

반대로 $S3 = x_{1}y_{n} + x_{2}y_{n-1} + ... + x_{a}y_{n-(a-1)} + ... + x_{b}y_{n-(b-1)} + ... + x_{n}y_{1}$

 

마찬가지로 $y_{n-(a-1)}$ 과 $y_{n-(b-1)}$을 서로 바꾸고 두 식을 빼면

 

$S3 - S4 = (x_{a} - x_{b})(y_{n-(a-1)} - y_{n-(b-1)}) <= 0$이므로 값이 반드시 커진다.

 

따라서, $x_{1}y_{1} + x_{2}y_{2} + ... + x_{n}y_{n}$이 최댓값이고, $x_{1}y_{n} + x_{2}y_{n-1} + ... + x_{n}y_{1}$이 최솟값이다.

 

 

3. 문제

 

12724번: Minimum Scalar Product (Large)

 

두 배열 X,Y가 주어질 때 두 배열 원소들의 곱의 합의 최솟값을 찾는 문제

 

위 재배열 부등식을 이용해서 X를 내림차순 정렬하고, Y를 오름차순 정렬한 다음 두 원소의 곱의 합이 최솟값

 

from sys import stdin

T = int(stdin.readline())

for t in range(1,T+1):
    
    n = int(stdin.readline())
    
    A = list(map(int,stdin.readline().split()))
    B = list(map(int,stdin.readline().split()))

    A.sort(reverse = True)
    B.sort()

    x = 0

    for i in range(n):
        
        x += A[i]*B[i]
    
    print(f'Case #{t}: {x}')

 

 

3603번: Journey with Pigs

 

돼지를 n개의 마을에 팔고자 하는데, 돼지 무게 1킬로당 p루블에 팔 수 있고, 각 마을까지 거리가 d킬로미터인데,

 

1킬로그램당 1킬로미터를 운반하는데 t루블 비용이 든다고 할때, 각 마을마다 1마리씩 팔아서 최대 이익을 얻고자한다.

 

각 돼지를 어디 마을에 팔아야하는가?

 

돼지 무게로 얻는 이익은 wp이고 1킬로그램당 d킬로미터를 운반한다면 dt 비용이 드는데, 돼지 무게는 w이므로

 

wdt만큼 비용이 들어서 이익은 wp - wdt = w(p-dt)

 

따라서, 각 돼지 $w_{1}, w_{2}, ..., w_{n}$과 각 마을마다 드는 이익 $p_{1} - d_{1}t, p_{2}-d_{2}t, ... , p_{n} - d_{n}t$

 

에 대하여 돼지 한마리당 마을 하나에 팔 수 있으므로, 결국 w와 p-dt의 곱의 합의 최댓값을 찾는 문제

 

그래서 W를 정렬하고, P-Dt를 정렬한 다음, 순서대로 곱하고 합하면 그것이 최대다.

 

n,t = map(int,input().split())

W = list(map(int,input().split()))
D = list(map(int,input().split()))
P = list(map(int,input().split()))

A = []
B = []

for i in range(n):
    
    w = W[i]
    A.append((w,i))

for i in range(n):
    
    p,d = P[i],D[i]

    B.append(((p-d*t),i))
    
A.sort()
B.sort()

answer = [0]*n

for i in range(n):
    
    answer[B[i][1]] = A[i][1]+1

print(*answer)