문제
풀이
•
나무 전체 길이 합이 int 범위를 넘어가기 때문에
•
long long 으로 해줘야한다.
•
left 이상 right 미만으로 풀었다.
구현
#include <iostream>
using namespace std;
int n;
long long m;
int wood[1000001];
int wood_max;
int rec(long long left, long long right) {
long long sum;
long long mid;
mid = (left + right) / 2;
if (right <= left + 1)
return (mid);
sum = 0;
for (int i = 0; i < n; i++)
if (wood[i] - mid > 0) sum += wood[i] - mid;
return (sum < m ? rec(left, mid) : rec(mid, right));
}
int solve() {
return (rec(0, wood_max + 1));
}
int main() {
wood_max = -1;
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> wood[i];
if (wood_max < wood[i]) wood_max = wood[i];
}
cout << solve() << endl;
return (0);
}
C++
복사