BOJ 23829 C++

문제접근

이분탐색 + 누적합으로 시간초과를 피할 수 있습니다.
1 3 7 9 10 이렇게 배열이 있을때 4의 위치에서 사진을 찍었다고 해봅시다.
그렇다면 4보다 작은 위치에있는 값들의 점수를 구하는 방법은 1-4, 3-4의 절대값이므로 4보다 작은 위치에있는 사진의 점수는 4겠네요. 이를 반복문으로 하지않고 누적합으로 게산하여야 합니다. 왼쪽에서 얻을 수 있는 점수의 최대값은

사진을 찍은 위치 x * 왼쪽 나무의 갯수 - 왼쪽 값들의 합.

즉 x가 4일때 나무가 왼쪽에 나무가 2개있을때 최대값은 8이고 그곳에서 나무들의 좌표의 합을 빼면 왼쪽에서의 점수가 됩니다.

그렇다면 오른쪽 나무들의 점수를 구하는 방법은 이러합니다.
오른쪽 나무에서 얻을 수 있는 최대의 값

전체 나무의 값의 합 - 왼족 나무 값의 합

거기에 오른쪽 나무들의 갯수만큼 x를 빼주면 되겠죠.
그 수는 다음과 같습니다 x * (전체 나무수 - 왼쪽 나무 수)

이 값을 오른쪽 값의 합에서 빼버리면 x보다 오른쪽에 있는 나무들에서 x를 하나씩 뺀것과 같습니다.

쉽게 떠올릴수 있는 아이디어 였지만. 생각이 너무 오래걸렸습니다.

코드

#include <bits/stdc++.h> 
#define ll long long
using namespace std;

int ebun(const vector<ll>& x, int target)
{
	int lo = 0;
	int hi = x.size() - 1;
	while (lo <= hi)
	{
		int mid = (lo + hi) / 2;
		if (x[mid] < target)
			lo = mid + 1;
		else
			hi = mid - 1;
	}
	return lo;
}



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, q; cin >> n >> q;
	vector<ll> v(n);
	vector<ll> pre(n + 1, 0);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
		
	}
	sort(v.begin(), v.end());
	for (int i = 1; i <= n; i++)
	{
		pre[i] = v[i - 1] + pre[i - 1];
	}
	while (q--)
	{
		ll num; cin >> num;
		int index = ebun(v, num);
		ll leftMax = pre[index];
		ll leftVal = index * num - leftMax;
		ll rightMax = pre[n] - leftMax;
		ll rightVal = rightMax - (num * (n - index));
		cout << leftVal + rightVal << "\n";
	}

}