BOJ 23830 C++

문제접근

태영이가 청소를 하지 않아도 되는 $K$의 최솟값을 출력한다.
$K$는 이분탐색에서 lowerBonud의 값이 되겠네요.
본문에 제시된것처럼 학생의 점수가 k보다 크면 학생의 점수에서 p를 빼고
작으면 q를 더하죠.
그렇다면 이분탐색의 범위를 이렇게 정해야겠네요.

lo = 1;
hi = 학생점수에서 가장 큰값 + 1;
hi를 이렇게 정의한 이유는 k미만일때 학생 전부의 점수를 더하게 하기 위함입니다.

코드

#include <bits/stdc++.h> 
#define ll long long
using namespace std;
ll over, under, r, s;
bool sol(const vector<ll>& x, ll k)
{
	ll size = x.size();
	ll sum = 0;
	for (ll i = 0; i < size; i++)
	{
		if (x[i] > k + r)
		{
			sum += x[i] - over;
		}
		else if (x[i] < k)
		{
			sum += x[i] + under;
		}
		else
		{
			sum += x[i];
		}
	}
	return sum >= s;
}

ll ebun(const vector<ll>& x, ll hi)
{
	ll lo = 1;
	hi = hi + 1;
	while (lo <= hi)
	{
		ll mid = (lo + hi) / 2;
		if (sol(x, mid))
		{
			hi = mid - 1;
		}
		else
			lo = mid + 1;
	}
	return lo;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	ll n; cin >> n;
	vector<ll> v(n);
	ll hi = 0;
	for (ll i = 0; i < n; i++)
	{
		cin >> v[i];
		hi = max(hi, v[i]);
	}

	cin >> over >> under >> r >> s;
	ll ans = ebun(v, hi);
	if (ans > hi + 1)
		cout << -1;
	else
		cout << ans;

}