P1182 数列分段（贪心+二分答案）

题目描述

分析

这题用二分法
首先，二分法需要有一个单调的序列，肯定不能对数列排序，数列不能变；
换一个方向：遍历每段和的最大值，通过最大值用贪心思想去确定段的个数，得到一个限制区间，在区间中求最小值；
首先，每段和的最大值的范围：当一个元素一段时，就是元素中的最大值；所有元素在一段中时，就是所有元素的和。并且通过观察，段的个数随着每段和的最大值单调递减（可能会相等）
如果直接遍历会超时，所以采用二分法。
因为是递减序列，所以条件跟递增相反，要求满足条件的第一个小于等于M值的数（或者直接二分搜索等于M的数）。

代码

#include<bits/stdc++.h> 
typedef long long ll;
using namespace std;
const int maxn = 1e5+50;
int n,m,a[maxn],maxall = 0;
ll sum = 0,ans = 0;
//采用贪心策略求段的个数 
bool check(int t){
	int s = 0,flag = 0;
	for(int i = 1;i<= n;i++){
		if(s+a[i] > t){
			flag++;
			s = a[i];
		}
		else{
			s += a[i];
		}
	}
	if(s!= 0)
		flag++;
	return flag <= m;
}
int main(){
	//freopen("a.txt","r",stdin); 
	std::ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i = 1;i<= n;i++){
		cin>>a[i];
		sum += a[i];
		maxall = max(maxall,a[i]);
	}
	//左值为元素中最大值，右值为所有元素的和 
	int l = maxall ,r = sum;
	while(l < r){
		int mid = l + (r-l)/2;	//防止溢出 
		if(check(mid)){
			r = mid;
		}
		else{
			l = mid+1;
		}
	}
	cout<<l<<endl;
	return 0;
}