题解 P1182 【数列分段 Section II】

thoq · 2020-02-18 14:54:32 · 题解

如果你不知道什么是二分答案，请先看其他题解，而我想借此题谈谈二分答案的本质，并发散思维，得到一些新的算法。

个人认为，二分答案由“二分”和“答案”组成。宏观上，二分，是对问题状态空间的一种遍历方式，主要作用是降低时间复杂度；答案，即枚举答案，则是一种解题方法，主要作用是化求解为判定，降低难度。

具体来讲：

• 答案。在此题中，我们首先要确定答案的范围。显然，答案最小可能是数列中的最大值（记为 l ），最大可能是所有数的和（记为 r）。其次，我们发现，给出一个解，判定这个解是否合法，在此题中显得简单。这启示我们用枚举答案再判定的方法解决此题。

• 二分。二分建立在答案的基础上。此题中答案的排布，是有一定规律的，即，存在一个分界点 p，使得 \left[l,p\right)中的数都是非法解，\left[p,r\right]中的数都是可行解。而 p 即为所求的最小解。这种性质启示我们用一种特定的方法来枚举答案，于是有了二分。

很多人便能够写出以下程序：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n,m,a[N];
bool check(int k)
{
    int cur=0,ans=1;
    for(int i=1;i<=n;i++)
    {
        if(cur+a[i]>k)
        {
            cur=0;
            ans++;
        }
        cur+=a[i];
    }
    return ans<=m;
}
int main()
{
    scanf("%d%d",&n,&m);
    int l=0,r=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        r+=a[i];
        l=max(l,a[i]);
    }
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid))
        {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}

至此，还没有结束。我们可以创新吗？

关于答案，这是此题的基本解决方式，似乎无从下手；而二分，只是枚举答案的一种方式，我们还可以换其他方式，比如，直接枚举。

    for(int i=l;i<=r;i++)
        if(check(i))
        {
            printf("%d\n",i);
            return 0;
        }

重复部分不再贴出。此代码 TLE60 分，因为枚举的方式过于朴素。不过，这很好体现了答案思想，更让我们思考，还有什么遍历状态空间（此题中体现为枚举答案）的方式呢？

有啊，比如倍增。

    int p=1,j=r;
    while(p)
    {
        int k=j-p+1;
        if(k>=l&&check(k))
        {
            ans=k;
            j-=p;
            p*=2;
        }
        else p/=2;
    }

此代码 AC，时间复杂度和二分答案相同，不妨称之“倍增答案”。倍增答案几乎能完成所有二分答案的题，但为什么没有广泛使用呢？大概是二分更好写吧。