【二分查找】[洛谷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;
   
}

           

总结

二分答案适用于

求最大值的最小情况

这类问题，因为这类情况满足二分搜索的有界性、确定性。因为答案的范围是确定的;