7730

static int N, M;
static int trees[1000000];

static int cmp(const void * p1, const void * p2)
{
	int n1 = *(int *)p1;
	int n2 = *(int *)p2;

	return n2 - n1;
}

static int solution(void)
{
	int H, ret = 0;
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++)
		scanf("%d", &trees[i]);

	qsort(trees, N, sizeof(int), cmp);

	int max = trees[0], min = 0;
	while (min <= max)
	{
		long long sum = 0;

		H = (min + max) / 2;
		for (int i = 0; i < N && trees[i] > H; i++)
			sum += (trees[i] - H);

		if (sum < M)
			max = H - 1;
		else
		{
			if (H > ret)
				ret = H;
			min = H + 1;
		}
	}

	return ret;
}

핵심은 이진 탐색과 같은 방식으로 한번에 잘라낼 높이를 구해야 한다.

그러지 않고 1씩 증가하는 방식으로 하게 된다면 타임아웃이 발생 할 가능성이 높다.

 

그리고 한가지 주의 할 부분은 잘라낸 후 생길 수 있는 원목의 총 길이이다.

문제 조건 상 십억 이하인 길이의 원목이 최대 백만개 까지 존재 할 수 있다.

 

그러면 H를 0으로 했을 때 생기는 원목의 총 길이가 최대 10^15이다. 

그렇기 때문에 생길 수 있는 원목의 총길이는 long long으로 담아야 한다.

 

여기롤 int로 해서 자꾸 pass를 받지 못했다.

다음부터는 입력의 조건을 보고 발생 할 수 있는 최대값을 미리 유추를 할 수 있어야겠다.