折半検索及び木切り・木材加工問題解

にぶん
半角検索
コードテンプレート

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メートルを上回らない部分は変わらない)を切り落とす.ミルコは木が切り落とされた部分まで行く.
例えば、1行の木の高さがそれぞれ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<=2000000)
2行目:N個の整数は、1本あたりの高さを表し、値は10000000を超えない.すべての木材の長さの和はMより大きいので、必ず解があります.
出力フォーマット
1行目:1つの整数で、木を切る最高の高さを表します.
入出力サンプル
入力＃15 20 4 42 40 26 46出力＃36
本題では,checkのチェック内容は,得られた木の高さの総和が問題に合致するか否かである.
コード#コード#

#include 
#include 
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です.原木の長さはすべて正の整数で、私たちが切断した小段の木の長さも正の整数であることを要求します.
例えば2本の原木の長さはそれぞれ11と21で、等長の6段に切断することが要求され、明らかに切断できる小段の木の長さは最長5である.
入力フォーマット
1行目は2つの正の整数NとK(1≦N≦100000,1≦K≦1000000)であり、Nは原木の数であり、Kは必要とされるセグメントの数である.
次のN行は、1行につき1~1000000の正の整数があり、1本の原木の長さを表す.
出力フォーマット
切断可能なセグメントの最大長さ.1 cmの長さの小段さえ切り出せなければ、「0」を出力します.
入出力サンプル
入力＃13 7 232 124 456出力＃114
この問題では,checkは切断されたセグメント数が問題の要求に合致するか否かを判断するために用いられる.
コード#コード#

#include 
#include 
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;
}