洛谷P1182 数列分段 Section II【贪心+二分】

题目链接:P1182 数列分段 Section II

《洛谷P1182 数列分段 Section II【贪心+二分】》

程序说明:

二分适用于区间有界单调,例如最大值最小或者最小值最大这类问题。

设区间所有数中的最大值为L,区间所有的数总和为R,则答案一定位于L和R之间。利用二分算法快速得出答案。check函数利用贪心的思想,即P1181 数列分段Section I的方法,判断mid是否满足题目要求,如果不满足则在相应的区间进行二分查找。

代码如下:

#include <iostream>
using namespace std;
const int N = 100010;
int a[N], n, m; 
bool check(int x) { 
	int tot = 0, cnt = 1;
	for(int i = 0; i < n; i++) { 
		tot += a[i];
		if(tot > x) { 
			cnt++;
			tot = a[i];
		}
	}
	//如果所分的段数大于m,返回true 
	return cnt > m;
}
int main() { 
	cin>>n>>m;
	int l = 0, r = 0, mid;
	//l是区间最大值,r是区间总和 
	for(int i = 0 ; i < n; i++) { 
		cin>>a[i];
		l = max(l, a[i]);
		r += a[i];
	}	
	while(l <= r) { 
		mid = l + r >> 1;
		if(check(mid)) l = mid + 1;
		else r = mid - 1;
	}
	cout<<l;
	return 0;
}
    原文作者:cutlery1137
    原文地址: https://blog.csdn.net/Komatsu_1137/article/details/104132953
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞