洛谷 題解 P1182 數列分段`Section II`

題目連結

-【題目描述】

對于給定的一個長度為N的正整數數列A-i，現要将其分成M(M≤N)M(M≤N)段，并要求每段連續，且每段和的最大值最小。

關于最大值最小：

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

将其如下分段：

[4 2][4 5][1]

第1段和為6，第2段和為9，第3段和為1，和最大值為99。

将其如下分段：

[4][2 4][5 1]

第1段和為4，第2段和為6，第3段和為6，和最大值為6。

并且無論如何分段，最大值不會小于6。

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

輸入輸出格式

輸入格式：

第1行包含兩個正整數N，M。

第2行包含N個空格隔開的非負整數A_i，含義如題目所述。

輸出格式：

一個正整數，即每段和最大值最小為多少。

輸入樣例：

5 3

4 2 4 5 1

輸出樣例：

6

說明

對于20%的資料，有N≤10；

對于40%的資料，有N≤1000；

對于100%的資料，N≤100000,M≤N,A_i之和不超過10^9 。

正文開始

這道題的主要内容：二分答案

首先我們觀察題目，題目要求求出最大值的最小值，這時我們就可以考慮是否用二分答案，而二分則要确定題目是否滿足單調性，這樣才能保證二分得出的是最優解。

然後再看題目，發現因為要求“A_i是非負數”，是以每增加一個數則區間和必定變大，滿足單調性。

接着我們考慮二分的應用

在二分開始前我們要先“猜”一個可能是答案的數，然後再二分。而“猜”也不能盲目瞎選一個數，而是要根據答案可能的範圍“猜”。

由題易得，

lef((左端點）可能答案最小值）=max{A1…n},

rag((右端點）可能答案最大值）=A1+A2+A3+…+An;

在此範圍内不斷枚舉答案便可得出正确結果，而為了避免逾時，我們采用二分。

具體解釋見代碼

代碼

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int rag=0,lef=0,n,m,a[100010],mid,sum=0,gup,flag;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        lef=max(lef,a[i]);//求左端點 
        rag+=a[i];//求右端點 
    }
    while(lef<=rag)//答案合法 
    {
        mid=(lef+rag)>>1;  
        sum=0;
		gup=1;//從第一組開始計數 
		flag=false;//确定下次答案選取位置 
        for(int i=1;i<=n;++i)
        {
            sum+=a[i];//目前區間和 
            if(sum>mid)//超過答案 
            {
                gup++;//新開一組 
                sum=a[i];
            }
            if(gup>m)//區間過多，說明答案過小 
            {
                flag=true;
                break;
            }
        }
        if(flag)//答案小 
        {
            lef=mid+1;
        }
        else //答案大
        {
            rag=mid-1;
        }
    }
    printf("%d",lef); 
    return 0;
}
           

謝謝觀看！

第一次寫題解，不好請見諒。歡迎提意見！φ(>ω<*)