[数据结构与算法]P1182 数列分段 Section II【题解】

做法：贪心+二分

题意解读：

这题是我发的上一篇题解的题目的升级版。大意为给定一个长度为$N$序列$a_i(i\in [1,N],i\in {\mathbb{N}}^{?})$,将其分成$M$段，要求每段连续，并且使每段和的最大值最小。

相信大家如果眼睛不瞎$(LJZ:我瞎呢)$都能看到上面加粗的五个字：最大值最小。当题目中出现了类似的字眼时，就表示大概率这题的答案具有单调性，可以二分解决。$(OW:今年tg必考二分)$

思路：

我们设这个最小值为$K$。我们略加思考可以发现：当$K$十分的小时，一定可以存在一种分组，使组数$M_K>M（举个例子：每个数自成一组。）$，此时的$K$值都是符合题意的。而当$K$逐渐增长到一个临界点以后，$M_K$将小于$M$，此时的$K$都不符合题意。所以这个临界点$(设为K_0)$满足:
$$\{\begin{array}{l}?M_x\in [1,M_0],M均符合题意。\\ ?M_x\in (M_0,+\infty ],M均不符合题意。\end{array}$$
受到这个$M_0$性质的启发，我们定义函数：

$$C(x)=\{\begin{array}{l}0,x>M_0\\ 1,x\le M_0\end{array}$$
然后取
$$\begin{gathered} l=x_{min}=\max (a_i)，即M=n。 \\ r=x_{max}=sum(a_i)，即M=1。 \end{gathered}$$

二分求出临界值即可。

$ACcode$:

#include<bits/stdc++.h>
using namespace std;

int n, m, a[100005],l,r;
long long s[100005];

inline void read()
{ 
    cin >> n >> m;
    for (int i = 1; i <= n;i++)
    {
        cin >> a[i];
        l = max(a[i], l);
        r += a[i];
    }
}

inline bool C(int x)
{
    int tot=0,num=0;
    for(int i=1;i<=n;i++)
    {
        if(tot+a[i]<=x)tot+=a[i];
        else tot=a[i],num++;
    }
    return num>=m;
}

int main()
{
    read();
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(C(mid))
        {
            l = mid+1;
        }
        else
        {
            r = mid-1;
        }
    }
    cout << l << endl;
    return 0;
}