下面是題解，為什么這一題可以用二分查找？不是要排序好的數列才可以用嗎？我看不太懂二分查找的實作程序，求解答
#include<bits/stdc++.h>
using namespace std;
long long n,bz,s=0,mid,leftt,longest,trees[1000008];
int main()
{
scanf("%lld%lld",&n,&bz);
for(int i=1;i<=n;i++)
{
scanf("%lld",&trees[i]);
longest=max(longest,trees[i]);//找到最長木材
}
while(leftt<=longest)
{
mid=(leftt+longest)/2; //從中間點開始作為伐木機高度
s=0;
for(int i=1;i<=n;i++)
if(trees[i]>mid) //樹的高度大于伐木機高度
s+=trees[i]-mid; //高的部分累加
if(s<bz) //木材不足
longest=mid-1;//在左邊搜 減小高度增加木材
else
leftt=mid+1;//在右邊搜 增加高度減小木材
}
cout<<leftt-1;
return 0;
}
uj5u.com熱心網友回復：
這個二分查找不是從trees中二分，而是高度的二分。即找到最大高度，那么leftt是從0開始到最大高度這不就是已經是順序的嗎？uj5u.com熱心網友回復：
噢噢原來是這個意思，那為什么最后return要leftt-1呢？為什么while的條件是letff＜=longest呢？
里面有很多細節不是很懂。比如它縮減區間
uj5u.com熱心網友回復：
還有while回圈體內為什么要s=0呢
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/256885.html
標籤：C語言
上一篇：CB茶館也蕭條了
下一篇：命令列啟動程式與雙擊程式運行問題