【二分查找】[洛谷P1182-數列分段]

題目連結

https://www.luogu.com.cn/problem/P1182
           

題目描述

輸入格式

解題思路

1.暴力法

0.DFS(x,k,tol)//從第x個元素開始，還需要找k段，此時的最大值為tol
1.循環m次，每次選擇一部分作為第i段的元素，找出此時的最大值；
2.當k=0時，記錄所有tol的最小值；
··········這樣隻能過一個樣例~~
           

代碼展示

void DFS(int x,int k,int tol){
	if(k<=0){
		if(x<=n)return;
		ans=min(ans,tol);
		return;
	}
	for(int i=x;i+k-1<=n;i++){//保證後面的段不為空 
		int ans=0;
		for(int j=x;j<=i;j++)
			ans+=num[j];
		DFS(i+1,k-1,max(tol,ans));
	}
}
           

2.二分查找

1.我們不難判斷出答案的範圍是[max(num[i]),sum(num[i])]；
2.利用二分搜尋判斷mid作為答案是否滿足條件；
3.然後不斷逼近，即為答案
4.解釋幾個疑惑：
	怎麼确定最終結果是數組能夠分段組成的？
	`假設過程中周遊到無法組成的數，那麼就會繼續往子序列周遊，因為二分查找是尋找最接近的情況，而隻有最大值的最小值最接近答案`
		
           

代碼展示

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
/*
思路:
	
*/    
int num[maxn]; 
int n,m;
bool check(int x){
	int tol=0,cal=0;
	for(int i=1;i<=n;i++){
		if(tol+num[i]<=x)tol+=num[i];
		else tol=num[i],cal+=1;
	}
	return cal>=m;
}                                                                    
int main(){
	cin>>n>>m;
	int l=0,r=0;
	for(int i=1;i<=n;i++){
		cin>>num[i];
		l=max(num[i],l);
		r+=num[i];
	}
	int mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid))l=mid+1;
		else r=mid-1;
	}
	cout<<l<<endl;
   return 0;
   
}

           

總結

二分答案适用于

求最大值的最小情況

這類問題，因為這類情況滿足二分搜尋的有界性、确定性。因為答案的範圍是确定的;