[BOJ 2805]木を切る
1227 ワード
https://www.acmicpc.net/problem/2805
分の探索により,midを基準として左,右区間で大きさを比較し,midをリセットし,正解を求めた.
に答える
コード(C+)
#include<bits/stdc++.h>
using namespace std;
long long int n, m;
int main() {
scanf("%lld %lld", &n, &m);
long long int maxN = 0;
long long int tree[n + 1];
for(int i = 0; i < n; i++) {
scanf("%lld", &tree[i]);
if(tree[i] > maxN) {
maxN = tree[i];
}
}
long long int left = 0;
long long int right = maxN;
long long int ans = 0;
while(left <= right) {
long long int mid = (left + right) / 2;
long long int total = 0;
for(int i = 0; i < n; i++) {
if(tree[i] > mid) {
total += tree[i] - mid;
}
}
// 나무가 남으면, 자르는 높이를 크게 설정
if(total >= m) {
ans = mid;
left = mid + 1;
}
else {
right = mid - 1;
}
}
printf("%lld", ans);
}
Reference
この問題について([BOJ 2805]木を切る), 我々は、より多くの情報をここで見つけました https://velog.io/@jsh15932/BOJ-2805-나무-자르기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol