洛谷P1182 数列分段Section II

清疚 2022-05-29 06:18 276阅读 0赞

## 题目描述 ##

对于给定的一个长度为N的正整数数列A\[i\]，现要将其分成M（M≤N）段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列4 2 4 5 1要分成3段

将其如下分段：

\[4 2\]\[4 5\]\[1\]

第一段和为6，第2段和为9，第3段和为1，和最大值为9。

将其如下分段：

\[4\]\[2 4\]\[5 1\]

第一段和为4，第2段和为6，第3段和为6，和最大值为6。

并且无论如何分段，最大值不会小于6。

所以可以得到要将数列4 2 4 5 1要分成3段，每段和的最大值最小为6。

## 输入输出格式 ##

输入格式：

输入文件divide\_b.in的第1行包含两个正整数N，M，第2行包含N个空格隔开的非负整数A\[i\]，含义如题目所述。

输出格式：

输出文件divide\_b.out仅包含一个正整数，即每段和最大值最小为多少。

## 输入输出样例 ##

输入样例\#1： 复制

5 3
    4 2 4 5 1

输出样例\#1： 复制

## 说明 ##

对于20%的数据，有N≤10；

对于40%的数据，有N≤1000；

对于100%的数据，有N≤100000，M≤N， A\[i\]之和不超过10^9。

思路：二分答案

参考题解：

1.[https://www.luogu.org/blog/xuxing/solution-p1182\#][https_www.luogu.org_blog_xuxing_solution-p1182]参考了一下前缀和数组的写法

2.[https://www.luogu.org/blog/user19523/solution-p1182][https_www.luogu.org_blog_user19523_solution-p1182]参考了二分的模板

区间：该数列最大值 至 所有数字之和为开始区间

这里所有数字之和可以用一下前缀和来求，而且在写check函数时不用一个个加来判断，直接用f\[i\]-f\[p-1\]来计算第i~p-1个数的和就行。

#include<algorithm>
    #include<iostream>
    using namespace std;
    
    int f[100001];
    int n, m;
    int Max, x;
    
    bool check(int mid)
    {
    	int sum = 1;int p = 1;//起始时有一段，p从1开始
    	for (int i = 2; i <= n;i++)
    	if (f[i] - f[p - 1] > mid)//如果第i~p个数的和>mid,就得到了一段,至于为什么p-1，用样例写一些就知道啦
    		p = i, sum++;
    	if (sum > m)//如果段数>需要的m段,说明mid略小,左边界就要等于mid+1继续二分
    		return true;
    	else
    		return false;
    }
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	cin >> n >> m;
    	for (int i = 1; i <= n; i++)
    	{
    		cin >> x;
    		if (Max < x)Max = x;
    		f[i] = f[i - 1] + x;
    	}
    
    	int l = Max, r = f[n];
    
    	while (l <= r)
    	{
    		int  mid = (l + r) / 2;
    		if (check(mid))
    			l = mid+1;
    		else
    			r = mid-1;
    	}
    	cout << l;
    	return 0;
    }

[https_www.luogu.org_blog_xuxing_solution-p1182]: https://www.luogu.org/blog/xuxing/solution-p1182#
[https_www.luogu.org_blog_user19523_solution-p1182]: https://www.luogu.org/blog/user19523/solution-p1182