소프티어

안녕하세요 [인증평가(4차) 기출] 슈퍼컴퓨터 클러스터 문제 질문있습니다

이진탐색으로 코드 작성했는데 성능의 max값을 잘못 설정한 것 같습니다

예산 N = 1이고, B가 10^18이고, a[1] = 10^9일 때 가능한 성능의 max 값이 2*10^9 인것 같습니다

그런데 이진탐색의 max값을 무작정 20억으로 하면 N이 높을 때 오버플로우가 발생하는 것 같습니다

그래서 이진탐색의 max값을 잘 설정해야 하는데 제 개인적인 생각으로는 루트(예산 나누기 n) + 기존 최대성능 하면 나올 수 있는 성능의 max가 된다고 생각하는데 제 생각이 어디가 틀렸는지 알려주시면 정말 감사하겠습니다

#include
#include
#include
#include


using namespace std;

int n;
long long coin;
vector a;

void solve() {
	long long money = 0;
	long long start = a.front();
	long long end = (long long)sqrt(n + coin / n) + a.back() + n;
	long long mid;
	long long result;

	while (start <= end) {
		mid = (start + end)/ 2;

		money = 0;
		for (int i = 0; i < n; i++) {
			if (a[i] < mid) {
				money += (mid - a[i]) * (mid - a[i]);
			}
			else {
				break;
			}
		}

		if (money < coin) {
			start = mid + 1;
			result = mid;
		}
		else if (money > coin) {
			end = mid - 1;
			result = mid - 1;
		}
		else {
			result = mid;
			break;
		}
	}

	printf("%lld", result);
	
}

int main(int argc, char** argv)
{
	scanf("%d %lld", &n, &coin);
	long long power;

	for (int i = 0; i < n; i++) {
		scanf("%lld", &power);
		a.push_back(power);
	}

	sort(a.begin(), a.end());

	solve();

	return 0;
}