글 읽기 - 나무 자르기

2015112119 8년 전 0

오답인 케이스가 있을까요..

#include <stdio.h>

int Trees[1000001];

int main() {
	int Number, Need_Trees;
	scanf("%d %d", &Number, &Need_Trees);
	int Max = 0, Min;

	for (int i = 0; i < Number; i++) {
		scanf("%d", &Trees[i]);
		Max = Max < Trees[i] ? Trees[i] : Max;
	}
	int Left = 0, Right = Max, Mid;
	while (1) {
		long long int Sum = 0;
		Mid = (Right + Left) / 2;
		for (int i = 0; i < Number; i++) {
			if ((Trees[i] - Mid) < 0)
				continue;
			Sum += Trees[i] - Mid;
		}
		
		if (Need_Trees > Sum) {
			Right = Mid - 1;
		}
		else {
			if (Need_Trees == Sum) {
				printf("%d\n", Mid);
				break;
			}
			else {
				if (Left == Mid) {
					printf("%d\n", Right);
					break;
				}
			}
			Left = Mid + 1;
		}
	}
}

whgusfud 8년 전 0

Right = Mid - 1이랑 Left = Mid + 1하신 거를 조금 더 생각해 보시면 될 거 같아요.

답이 H = 8에서 60의 나무를 가져갈 수 있고, H = 9에서 58의 나무를 가져갈 수 있다고 가정합시다.

이 때, 목수는 59만큼의 나무를 가져가고 싶어합니다.

딱 떨어지는 답이 없기 때문에, 적어도 59의 나무를 가져갈 수 있는 H = 8이 답이 됩니다.

이 경우를 위 코드에 대입했을 때, Right = 9, Mid = 8, Left = 7이 되었다고 가정합시다. Need_Trees > Sum이기 때문에 Right = Mid - 1 = 7이 됩니다.

그러면 이제 이 문제를 풀 방법이 위 코드에는 없어집니다...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

나무 자르기

2015112119 8년 전 0

whgusfud 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말