[BOJ]2805-나무 자르기

2805

바로 이분탐색으로 시작했지만, LLONG_MAX 가 컴파일 에러가 나서 실패.

다음에는 경계값으로 인해 무한 루프를 돌거나 답을 못 찾아서 실패.

질문 게시판의 반례는 신이야!

성공 코드

#include <iostream>
#include <vector>
using namespace std;

vector<long long> vec;

long long length = -1;
long long res = -1;
int N, M;

void search()
{
	long long maxLength = -1;
	long long startLength = 0;
	long long endLength = length;

	bool flag = false;

	while (startLength <= endLength)
	{
		long long tmp = 0;

		long long cur = (startLength + endLength) /2;

		if (startLength == endLength)
		{
			flag = true;
		}


		for (long long item : vec)
		{
			if (item > cur)
			{
				tmp += item - cur;
			}
		}

		if (tmp == M)
		{
			res = cur;
			return;
		}
		else if (tmp < M)
		{
			endLength = cur -1;
		}
		else
		{
			if (cur > maxLength)
			{
				maxLength = cur;
			}

			startLength = cur + 1;

		}

		if (flag)
		{
			break;
		}
	}

	res = maxLength;
	
}


int main()
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);
	
	cin >> N >> M;

	for (int i = 1; i <= N; i++)
	{
		long long tmp;
		cin >> tmp;

		vec.push_back(tmp);

		if (tmp > length)
		{
			length = tmp;
		}
	}

	search();
	
	cout << res;
}