2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
학회 스터디 강의할 때 다룬 문제
이 문제를 잘 설명하고 싶어서...
ppt.. 정말 열심히 만들었다.
이분탐색을 접목해 가능한 높이 중 일부만 확인하는 게 포인트.
int arr[1000000];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m;
int left, right, maxH = 0;
int ans = 0;
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> arr[i];
maxH = max(maxH, arr[i]);
}
left = 0;
right = maxH + 1;
while (left < right) {
int mid = (left + right) / 2;
ll sum = 0;
for (int i = 0; i < n; i++) {
if (arr[i] > mid) {
sum += (ll)arr[i] - mid;
}
}
if (sum >= m) {
ans = max(ans, mid);
left = mid + 1;
}
else {
right = mid;
}
}
cout << ans;
return 0;
}