C++ 2805 나무 자르기 [이분 탐색], 범위 long long 사용

 

 

 

시간 초과

#include <iostream>
#include <vector>
#include <algorithm>

int SerchCount(std::vector<int>& _nums, int _M)
{
	int st = 0;
	int end = _nums.size()-1;

	int Mid = (st + end) / 2;

	int Height = _nums[Mid];

	while (true)
	{
		int Check = 0;

		for (int i = 0; i <=end; i++)
		{
			if (_nums[i] > Height)
			{
				Check += (_nums[i] - Height);
			}
		}

		if (Check < _M)
		{
			--Height;
		}
		else if (Check > _M)
		{
			++Height;
		}
		else
		{
			break;
		}
	}

	return Height;
}

int main()
{
	std::vector<int> nums;
	int N, M;

	std::cin >> N >> M;

	nums.resize(N);

	for (int i = 0; i < N; i++)
	{
		std::cin >> nums[i];
	}

	std::sort(nums.begin(), nums.end());

	int result = SerchCount(nums, M);

	std::cout << result;
	return 0;
	
}

 

 

정답

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

long long SerchCount(std::vector<long long>& _nums, long long _M)
{
	long long st = 0;
	long long end = _nums[_nums.size() - 1];

	long long Height = 0;

	while (st <= end)
	{
		long long Check = 0;
		long long Mid = (st + end) / 2;

		for (int i = 0; i < _nums.size(); i++)
		{
			if (_nums[i] > Mid)
			{
				Check += (_nums[i] - Mid);
			}
		}

		if (Check < _M)
		{
			end = Mid - 1;
		}
		else
		{
			Height = Mid;
			st = Mid + 1;
		}
	}

	return Height;
}

int main()
{
	std::vector<long long> nums;
	long long  N, M;

	std::cin >> N >> M;

	nums.resize(N);

	for (int i = 0; i < N; i++)
	{
		std::cin >> nums[i];
	}

	std::sort(nums.begin(), nums.end());

	long long result = SerchCount(nums, M);

	std::cout << result;
	return 0;

}