Boj 2805) Eko

문제

백준 2805

방법 1

설명

Bineary Search 를 해야하는데 문제 조건이 그 수와 같은 값이 아니라 같거나 큰 값임.

그래서 바로 적용하면 문제가 생김.

이때 아이디어는 ans 를 특정 조건에만 업데이트 하는 것임.

1. mid 에서의 계산값이 m 보다 클 때
2. ans 가 mid 보다 작으면 mid 값으로 업데이트

시간 복잡도

O(n*logn)

코드

long long arr[1000001];
int n, m;

long long Calc(long long h)
{
	long long ans = 0;
	for (int i = 0; i < n; i++)
		ans += max(arr[i] - h, 0ll);
	return ans;
}

int main()
{
	fastio;

	cin >> n >> m;
	
	long long t1 = 0, t2 = 3e9, t3;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		t2 = max(arr[i], t2);
	}
	
	long long calced, ans = 0;
	while (t1 <= t2)
	{
		t3 = (t1 + t2) / 2;
		calced = Calc(t3);
		if (calced < m)
			t2 = t3 - 1;
		else {
			if (t3 > ans) ans = t3;
			t1 = t3 + 1;
		}
	}
	cout << ans;
}

방법 2

설명

먼저 주어진 인풋을 내림차순으로 정렬을 함.

그리고 큰 나무부터 차례로 모으면, 지금까지 모은 나무의 갯수 * 다음 나무와의 높이 차 만큼 나무를 모을 수 있음.

그러다가 원하는 나무양을 초과하면 다음 나무와의 높이 차 를 적절히 조절하면 됨.

시간 복잡도

O(n*logn)

코드

long long arr[1000001];
long long n, m;

int main()
{
	fastio;

	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	
	sort(arr, arr + n+1, [](int a, int b) { return a > b; });
	
	int acc = 0, acc_sum = 0;
	while(1) {
		acc++;
		if (m <= acc_sum + acc * (arr[acc-1] - arr[acc]))
		{
			cout << -(int)ceilf(float(m - acc_sum) / float(acc)) + arr[acc-1];
			break;
		}
		else {
			acc_sum += acc * (arr[acc-1] - arr[acc]);
		}
	}
}