이진검색 - drying

프로그램 명: drying

제한시간: 1 초

겨울에 빨래 한 후 옷을 말리는 것은 힘든 작업이다.

그러나 제인은 매우 깔끔한 성격이라 이 지루한 작업을 싫어하지 않는다. 그녀는 라디에이터를 이용해서 이 작업을 더 빨리 하기로 하였다. 그러나 라디에이터가 작아서 한 번에 한 벌의 옷만을 말릴 수 있다.

제인은 가능한 빠른 시간안에 모든 옷을 말리기를 원한다. 당신에게 젖은 옷들이 주어질 때 모든 옷을 말리는데 필요한 가장 빠른 시간을 계산 해 줄 것을 요청했다.

제인은 빨래 후 젖은 n 벌의 옷이 있다. 각 옷은 ai 만큼의 물을 머금고 있다. 매 분당 각 옷의 물의 양은 1 만큼 준다.(물론 , 옷이 아직 완전히 마르지 않은 상태에서 )

물의 양이 제로가 될 때 옷이 완전히 말려진 것이다.

매 분당 제인은 하나의 옷을 라디에이터에 말리기 위해서 선택할 수 있고, 라디에이터는 매우 뜨거워서, 매분 물의 양이 k 만큼 준다. 물의 양은 0 미만이 될수 없고 이 경우 물의 양은 0 이 된 것이다.

일은 라디에이터를 효과적으로 이용해서 옷 말리는 시간을 줄여야 하는 것이다. 옷 말리는 작업은 모든 옷을 말릴 때까지 계속 된다.

입력

• 첫 라인은 정수 n 이 주어진다. (1 ≤ n ≤ 100 000).
• 두 번째 줄에는 ai 가 주어진다.(1 ≤ ai ≤ 10⁹)
• 세 번째 라인은 k 가 주어진다.(1 ≤ k ≤ 10⁹).

출력

모든 옷을 말리는 데 필요한 최소 시간을 출력한다.

입출력 예

입력

3
2 3 9
5

출력

3

입력

3
2 3 6
5

출력

2

출처: Northeastern Europe 2005, Northern Subregion

package drying;

import java.util.Arrays;

import java.util.Scanner;

class Main {

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner scanner = new Scanner(System.in);

int n = Integer.parseInt(scanner.nextLine());

String[] tokens = scanner.nextLine().split(" ");

int k = Integer.parseInt(scanner.nextLine());

scanner.close();

int arr[] = new int[n];

int i=0;

while(i<n) {

arr[i]=Integer.parseInt(tokens[i]);

i++;

}

int count=0,sum=0;

Arrays.sort(arr);

while(true)

{

if(arr[n-1] < arr[n-2])

Arrays.sort(arr);

for(i=0;i<n-1;i++) {

if(arr[i]>0) {

arr[i]=arr[i]-1;

sum += arr[i];

}

else if(arr[i]==0)

sum += arr[i];

}

arr[n-1]=arr[n-1] - k;

if(arr[n-1]<0)

arr[n-1]=0;

sum += arr[n-1];

count++;

if(sum<=0)

break;

else

sum=0;

}

System.out.println(count);

}

}