二分查找P1873 [COCI2011-2012#5] EKO / 砍树

P1873 [COCI2011-2012#5] EKO / 砍树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这个题就是给新手练手的，在那个位置上在进行，寻找合适的砍树高度，下面在介绍一个二分查找的模板

int binarySearch(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid; // 找到目标值，返回索引} else if (nums[mid] < target) {left = mid + 1; // 目标值在右半部分，更新左边界} else {right = mid - 1; // 目标值在左半部分，更新右边界}}return -1; // 没有找到目标值
}

#include<bits/stdc++.h>
using namespace std;
long long n,m,tree[1000000+10],l,r,mid;
int main()
{scanf("%ld%ld",&n,&m);for(long long  i=1;i<=n;i++){scanf("%lld",&tree[i]);r=max(tree[i],r);}while(l<=r){mid=(r+l)>>1;long long temp=0;for(int i=1;i<=n;i++){if(tree[i]>mid){temp+=tree[i]-mid;}}if(temp<m){r=mid-1;}else l=mid+1;}printf("%lld",r);return 0;
}

这个代码的奇特之处在于这个temp的更新，不断的在中间位置靠拢，虽然这个也是二分查找的思想但是在这本蒟萝也想了好久