二分
折半查找
代碼模板
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid))
{
ans=mid;
l=mid+1;
}
else
{
r=mid-1;
}
}
砍樹
https://www.luogu.com.cn/problem/P1873
題目描述
伐木工人米爾科需要砍倒M米長的木材，這是一個對米爾科來說很容易的作業，因為他有一個漂亮的新伐木機，可以像野火一樣砍倒森林，不過，米爾科只被允許砍倒單行樹木，
米爾科的伐木機作業程序如下：米爾科設定一個高度引數H（米），伐木機升起一個巨大的鋸片到高度H，并鋸掉所有的樹比H高的部分（當然，樹木不高于H米的部分保持不變），米爾科就行到樹木被鋸下的部分，
例如，如果一行樹的高度分別為20，15，10和17，米爾科把鋸片升到15米的高度，切割后樹木剩下的高度將是15，15，10和15，而米爾科將從第1棵樹得到5米，從第4棵樹得到2米，共得到7米木材，
米爾科非常關注生態保護，所以他不會砍掉過多的木材，這正是他為什么盡可能高地設定伐木機鋸片的原因，幫助米爾科找到伐木機鋸片的最大的整數高度H，使得他能得到木材至少為M米，換句話說，如果再升高1米，則他將得不到M米木材，
輸入格式
第1行：2個整數N和M，N表示樹木的數量（1<=N<=1000000）,M表示需要的木材總長度（1<=M<=2000000000）
第2行：N個整數表示每棵樹的高度，值均不超過1000000000，所有木材長度之和大于M，因此必有解，
輸出格式
第1行：1個整數，表示砍樹的最高高度，
輸入輸出樣例
輸入 #1
5 20
4 42 40 26 46
輸出 #1
36
本題中，check的檢查內容即為 所得到的樹的高度總和 是否符合題目
代碼
#include <iostream>
#include <string>
using namespace std;
int n,m;
int ans=0;
int l=0,r=0;
int tree[1000005]={0};//注意資料范圍
bool check(int x)
{
long long s=0;//注意資料范圍
for(int i=1;i<=n;i++)
{
if(tree[i]>x)//判斷第i棵的高度是否比鋸片的高度高
{
s+=tree[i]-x;//將樹砍下的高度累加
}
}
return s>=m;//將高度和與需求高度m比較
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>tree[i];
r=max(r,tree[i]);//存放最大值！
}
while(l<=r)//簡單的對半查找
{
int mid=(l+r)/2;
if(check(mid))
{
？;
l=？;
}
else
{
r=？;
}
}
cout<<ans;//完美輸出！
return 0;
}
搞定一題，下一題：
木材加工
https://www.luogu.com.cn/problem/P2440
題目背景
要保護環境
題目描述
木材廠有一些原木，現在想把這些木頭切割成一些長度相同的小段木頭（木頭有可能有剩余），需要得到的小段的數目是給定的，當然，我們希望得到的小段木頭越長越好，你的任務是計算能夠得到的小段木頭的最大長度，木頭長度的單位是cm，原木的長度都是正整數，我們要求切割得到的小段木頭的長度也是正整數，
例如有兩根原木長度分別為11和21，要求切割成到等長的6段，很明顯能切割出來的小段木頭長度最長為5.
輸入格式
第一行是兩個正整數N和K(1 ≤ N ≤ 100000，1 ≤ K ≤ 100000000)，N是原木的數目，K是需要得到的小段的數目，
接下來的N行，每行有一個1到100000000之間的正整數，表示一根原木的長度，
輸出格式
能夠切割得到的小段的最大長度，如果連1cm長的小段都切不出來，輸出”0”，
輸入輸出樣例
輸入 #1
3 7
232
124
456
輸出 #1
114
此題中，check用來判斷 被切割的段數是否符合題目要求
代碼
#include <iostream>
#include <string>
using namespace std;
int n,k;//N是原木的數目，K是需要得到的小段的數目
int treelen[100005]={0};
int l=0,r=0;
int ans=0;
bool check(int x)
{
int s=0;
for(int i=1;i<=n;i++)
{
if(x<=treelen[i]&&x!=0)//若能切割且切割長度>=1
{
s+=(treelen[i]/x);//段數
}
else if(x==0)//無法切割（長度<1）
{
return s=0;//無法切割即段數為0
}
}
return s>=k;//回傳條件！！！！
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>treelen[i];
r=max(r,treelen[i]);//存放最大值
}
while(l<=r)//簡單的對半查找
{
int mid=(l+r)/2;
if(check(mid))
{
？;
l=？;
}
else
{
r=？;
}
}
cout<<ans;//完美輸出
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/37309.html
標籤：其他