백준 3090 차이를 최소로

https://www.acmicpc.net/problem/3090 3090번: 차이를 최소로 각각의 테스트 케이스에 대해서, 점수는 (100×(S+1)/(D+1))/(데이터 개수) 점이다. 이때, D는 출력한 수열에서 인접한 수의 차이의 최댓값, S는 정답이다. 즉, 출력한 수열이 정답인 경우 10점을 얻게 www.acmicpc.net 재밌는 파라메트릭 문제다. k를 매개변수로 잡고 차이가 k보다 작거나 같도록 만들 수 있는지에 대해 파라메트릭 서치를 하면 된다. 그러면 k가 주어졌을 때 그 여부를 알아내는 알고리즘을 작성해야 하는데, 이는 다익스트라에서 아이디어를 구했다. 전부 우선순위 큐에 때려박고, 작은 지점부터 보면서 양쪽에 k보다 차이가 큰 지점이 있으면 그 지점을 낮춰 주고 Update하고 큐..

원문링크 : 백준 3090 차이를 최소로