[백준] 2512번 예산 (이분 탐색)

-문제

 

-코드

#include<stdio.h>
#include<vector>
using namespace std;

vector<int> a;
int calcul(int n)
{
	int total = 0;
	for (int i = 0; i < a.size(); i++)
	{
		total += min(a[i], n);
	}
	return total;
}

int main() 
{
	int n, m, tmp, total=0, res, max = 0;
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &tmp);
		a.push_back(tmp);
		total += a[i];
		if (max < a[i]) max = a[i];
	}

	scanf("%d", &m);
	if (total <= m)
	{
		printf("%d", max);
		return 0;
	}
	
	int rt=max, lt=1, mid;
	
	while (lt<=rt)
	{
		mid = (rt + lt) / 2;
		if (calcul(mid) <= m)
		{
			lt = mid + 1;
			res = mid;
		}
		else
		{
			rt = mid - 1;
		}
	}

	printf("%d", res);
	return 0;
}