[白俊]2805 C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits> // INT_MAX를 위함
using namespace std;
// 나무 자르기
// 자꾸만 답이 1만 나와서 질문에 있는 코드가 저랑 비슷하길래 좀 참고,,
// int treelen과 int ans -> long long
vector<int> tree;
long long treelen;
int N, M;
long long ans;
void search(long long start, long long end) {
long long mid;
// while에서 if로 수정
if(start<=end) {
treelen = 0;
mid = (start + end) / 2;
// 잘리고 남은 나무의 길이를 다 더하기 위한 for문
for(int i=0; i<tree.size(); i++) {
if(tree[i]-mid < 0) continue;
treelen += tree[i]-mid;
}
// treelen이 필요한 길이 M보다 크거나 같으면 ans에 mid값을 넣고 절단기 높이를 늘려 또 탐색
if (treelen >= M) {ans = mid; search(mid+1, end);}
// else if (treelen > M) search(mid+1, high);
else search(start, mid-1); // treelen이 필요한 길이 M보다 모자랄 때 절단기 길이를 줄여 탐색
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> N >> M;
for(int i=0; i<N; i++) {
cin >> t;
tree.push_back(t);
}
sort(tree.begin(), tree.end());
// INT_MAX는 int의 최댓값. climits 헤더에 선언되어 있음.
// 원래 정렬된 벡터의 [0]과 젤 끝 값을 넣었음.
search(0, INT_MAX);
cout << ans << '\n';
return 0;
}
今度の勉強は木を切るのが一番難しい問題だ.Reference
この問題について([白俊]2805 C++), 我々は、より多くの情報をここで見つけました https://velog.io/@dbsrud11/백준-2805-Cテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol