8048 : 건물 높이 통일
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
일렬로 나열된 $N$개의 건물이 있습니다. 각 건물 $i$의 현재 높이는 $H_i$이며, 건물의 높이를 1만큼 증가시키거나 감소시키는 데 필요한 비용은 $C_i$입니다.
모든 건물의 높이를 어떤 하나의 임의의 동일한 높이 $X$로 바꾸려 합니다. 이때 필요한 최소 조절 비용의 총합을 구하는 프로그램을 작성하시오.
[제약 조건]
• 테스트 케이스 수 $T$
• $1 \le N \le 10{,}000$
• $0 \le H_i \le 10{,}000$
• $1 \le C_i \le 1{,}000$
모든 건물의 높이를 어떤 하나의 임의의 동일한 높이 $X$로 바꾸려 합니다. 이때 필요한 최소 조절 비용의 총합을 구하는 프로그램을 작성하시오.
[제약 조건]
• 테스트 케이스 수 $T$
• $1 \le N \le 10{,}000$
• $0 \le H_i \le 10{,}000$
• $1 \le C_i \le 1{,}000$
입력 설명
첫째 줄에 테스트 케이스의 개수 $T$가 주어집니다.
각 테스트 케이스마다:
첫째 줄에 건물의 수 $N$이 주어집니다. ($1 \le N \le 10,000$)
둘째 줄에 각 건물의 높이 $H_1, H_2, \ldots, H_N$이 공백으로 구분되어 주어집니다. ($0 \le H_i \le 10,000$)
셋째 줄에 각 건물의 단위당 높이 조절 비용 $C_1, C_2, \ldots, C_N$이 공백으로 구분되어 주어집니다. ($1 \le C_i \le 1,000$)
각 테스트 케이스마다:
첫째 줄에 건물의 수 $N$이 주어집니다. ($1 \le N \le 10,000$)
둘째 줄에 각 건물의 높이 $H_1, H_2, \ldots, H_N$이 공백으로 구분되어 주어집니다. ($0 \le H_i \le 10,000$)
셋째 줄에 각 건물의 단위당 높이 조절 비용 $C_1, C_2, \ldots, C_N$이 공백으로 구분되어 주어집니다. ($1 \le C_i \le 1,000$)
출력 설명
각 테스트 케이스마다 모든 건물의 높이를 통일시키는 데 드는 최소 비용을 한 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
1
4
1 2 3 4
10 10 10 10
출력 예시
COPY
복사되었습니다!
복사되었습니다!
20도움
높이 $X$에 따른 총 비용 함수 $f(X) = \sum C_i \times |H_i - X|$ 는 극솟값(최솟값)이 단 하나만 존재하는 아래로 볼록한 볼록 함수(Convex Function)입니다.
이와 같은 볼록 함수에서 최솟값을 구할 때는 **삼분 탐색(Ternary Search)**을 유용하게 적용할 수 있습니다. 탐색 구간 $[low, high]$를 삼등분하는 두 점
이와 같은 볼록 함수에서 최솟값을 구할 때는 **삼분 탐색(Ternary Search)**을 유용하게 적용할 수 있습니다. 탐색 구간 $[low, high]$를 삼등분하는 두 점
m1 = low + (high - low)/3, m2 = high - (high - low)/3을 잡고 f(m1)과 f(m2)를 비교해가며 구간을 매번 3분의 2로 줄여나가 $O(N \log(\text{max\_H}))$ 시간에 최적의 높이와 최소 비용을 찾아낼 수 있습니다.