[2805] 나무 자르기

• 입력: 나무 개수 N, 총 자르려는 나무의 합 M, N개의 나무 길이
• 출력: 적어도 M 길이의 나무를 자를 수 있는 최댓값
• 알고리즘: 이분법, 이분탐색
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> #include <algorithm> using namespace std; typedef long long ll; int main() { int N, M; scanf("%d%d", &N, &M); vector<ll> tree(N); for (int i = 0; i < N; i++) scanf("%lld", &tree[i]); sort(tree.begin(), tree.end()); ll lo = 1, hi = 2000000000, mid; while ((hi - lo) > 1) { mid = (lo + hi) / 2; ll total = 0; for (auto it = lower_bound(tree.begin(), tree.end(), mid); it != tree.end(); it++) total += *it - mid; if (total < M) hi = mid; else lo = mid; } printf("%lld\n", lo); return 0; }
• 문제 참고: https://www.acmicpc.net/problem/2805