[BOJ] 28703 - Double It

https://www.acmicpc.net/problem/28703

BOJ - 28703 - Double It

문제 유형: 정렬, 우선순위 큐, 슬라이딩 윈도우, 그리디

문제 난이도: Gold III

시간 제한: 1초

메모리 제한: 1024MB

 

문제

양의 정수로 이루어진 길이가 N$N$인 배열 A1,⋯,AN이 주어집니다. 당신은 원하는 만큼 다음 조작을 할 수 있습니다.

• 배열에서 원하는 수 하나를 골라서 2를 곱합니다.

조작 이후 A1,⋯,AN의 최댓값과 최솟값의 차이로 가능한 최솟값을 구하세요.

 

입력

첫 줄에 배열의 길이 N이 주어집니다. (1≤N≤200000)

둘째 줄에 N개의 양의 정수 A1,A2,⋯,AN이 주어집니다. (1≤Ai≤10^9)

 

출력

조작 이후 A1,⋯,AN의 최댓값과 최솟값의 차이로 가능한 최솟값을 구하세요.

 

풀이

 

 

한 피벗을 목표로 두고, 그에 각각 최대한 가깝게 맞추는 것을 목표로 할 것이다.

가장 큰 수를 기준으로 만들 것이다.

예제 {31, 41, 51, 92, 65, 3}에서, 가장 큰 숫자는 92인데, 이 숫자 전후로 2의 배수를 곱해서 후보군들을 나열할 것이다.

41이면, 82와 164가 92 전후의 수가 된다. 둘 다 후보 배열에 넣는다. 이를 모든 요소에 대해서 한다.

그 후보군 배열을 정렬하면, 위의 그림처럼 구성되는데, n길이의 슬라이딩 윈도우가 모든 요소를 하나씩 포함한다는 것을 알 수 있다.

이 슬라이딩 윈도우를 밀면서, 최소 차이를 구해주면 된다.

 

코드

Go

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n int32
	fmt.Fscan(reader, &n)

	maxElem := int32(0)
	a := make([]int32, n)
	for i := int32(0); i < n; i++ {
		fmt.Fscan(reader, &a[i])
		maxElem = max(maxElem, a[i])
	}

	b := make([]int32, 2*n)

	for i := int32(0); i < n; i++ {
		resized := a[i]
		for resized*2 < maxElem {
			resized *= 2
		}

		b[i*2] = resized
		b[i*2+1] = resized * 2
	}

	sort.Slice(b, func(i, j int) bool {
		return b[i] < b[j]
	})

	ans := int32(1e9)

	for i := int32(0); i < n; i++ {
		l := 0 + i
		r := n - 1 + i
		ans = min(ans, b[r]-b[l])
	}
	fmt.Fprintln(writer, ans)
}