문제
게임회사 사장인 쟁구가 만든 어떤 게임의 이름은 공항 타이쿤이다. 게임은 아주 간단하며, 다음과 같다.
긴 직선 모양의 정올국에 몇 개의 공항을 세우려고 한다. 정올국을 수직선으로 생각했을 때, 각 정수 좌표들에는 주요 도시들이 위치해 있다. 이 주요 도시들 중 어느 곳에든지 공항을 세울 수 있다. 비행기들이 이륙 후 바로 착륙할 때 최소 d의 거리가 필요하므로, 두 공항 사이의 거리가 d 이상이어야만 두 공항 사이를 비행기로 이동할 수 있다.
게임 내에서 2001년에 하나의 공항을 정올국에 가지고 시작한다. 다음 해부터, 매 해마다 새로운 공항이 어떤 위치에 세워진다. 이 때 어떤 두 공항 (a,b)를 고르더라도 a에서 b로 직접 또는 다른 공항을 경유해서 비행기로 여행이 가능해야 한다. 이 조건을 만족시키지 못한다면, 공항을 다른 위치로 옮겨야 한다. 원래 공항의 위치를 x, 옮기고자 하는 위치를 y라 할때 공항을 다른 위치로 이동시키는데는 |x-y|만큼의 값이 든다. 한 해마다, 공항을 최소비용으로 옮겨야만 다음 스테이지인 다음 해로 넘어갈 수 있다. 다음 해로 넘어가면, 플레이어가 이전에 옮겼던 공항들은 전부 원위치로 돌아간다. n개의 스테이지(즉 n년)을 넘기면 클리어한다.
매 해마다 추가되는 공항의 위치가 주어졌을 때, 그 해의 공항을 옮기는 최소 비용을 각각 구하는 프로그램을 작성하라.
[입력예2 보충설명 그림]
입력
플레이어가 여러 판을 플레이하므로, 입력도 q개의 테스트 케이스의 형식으로 들어온다.
첫 줄에 q가 주어지며, q는 테스트케이스의 개수이다.
그 다음 줄부터 각 테스트 케이스 별로 두 줄이 들어온다. 첫 줄엔 n과 d가 주어지며, n은 스테이지의 수, d는 두 공항간 비행기 통행이 가능한 최소 거리이다.
두번째 줄에는 매 해마다 공항의 위치가 들어온다. 총 n 스테이지이므로, n개의 정수가 공백을 사이에 두고 입력된다.
3 <= n <= 2 * 10^5, |xi| <= 10^8, 0 <= d <= 10^8
모든 테스트케이스의 n을 다 합쳐도 2 * 10^5를 넘지 않는다.
부분 문제: 35%의 테스트 케이스에 있어서 3 <= n <= 2 * 10^3을 만족한다.
출력
한 테스트 케이스 당 한 줄에 걸쳐서 n개의 숫자를 공백으로 구분해서 출력한다.
각 줄의 i번째 숫자는 i번째 해에 공항을 옮기는 최소비용이다.
예제 #1
1
3 1
0 0 0
0 1 1
예제 #2
1
5 4
1 -1 2 -1 1
0 2 2 3 3
출처
Hackerrank Week Of Code 35
로그인해야 코드를 작성할 수 있어요.