# 數列分段 Section II ## 題目描述 對於給定的一個長度為N的正整數數列 $A_{1\sim N}$，現要將其分成 $M$（$M\leq N$）段，並要求每段連續，且每段和的最大值最小。 關於最大值最小： 例如一數列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段。 將其如下分段： ...
數列分段 Section II
題目描述
對於給定的一個長度為N的正整數數列 \(A_{1\sim N}\)，現要將其分成 \(M\)（\(M\leq 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\)。
輸入格式
第 \(1\) 行包含兩個正整數 \(N,M\)。
第 \(2\) 行包含 \(N\) 個空格隔開的非負整數 \(A_i\)，含義如題目所述。
輸出格式
一個正整數，即每段和最大值最小為多少。
樣例 #1
樣例輸入 #1
5 3
4 2 4 5 1
樣例輸出 #1
6
提示
對於 \(20\%\) 的數據，\(N\leq 10\)。
對於 \(40\%\) 的數據，\(N\leq 1000\)。
對於 \(100\%\) 的數據，\(1\leq N\leq 10^5\)，\(M\leq N\)，\(A_i < 10^8\)， 答案不超過 \(10^9\)。
解析&代碼
二分答案
先介紹下二分答案吧
比如我們要從一本英漢詞典上查一個單詞，如果你從頭到尾一頁一頁的翻著找（並仔細一點），這樣找可以保證一定能找到，但是最壞情況你要把整本詞典都翻一遍，那就麻煩了（而且很累）。
有什麼改進的方法嗎？當然有。
我們考慮把這個詞典從中間分開，看一下中間那一頁的主要單詞都是啥，然後去判斷我要找的單詞應該在左半部分還是右半部分，再去那一部分考慮怎麼找就好了。同樣的，在另一部分也是要進行劃分並且判斷的操作。這樣一直進行下去，便能很快的找到答案，而且根本不需要翻過整個詞典來。
可以證明，如果一頁一頁的找，最多要找 \(n\) 次，但是用這個方法，最多找\(floor(log2n)\)次。
我們把這個方法叫做“二分答案”。顧名思義，它用二分的方法枚舉答案，並且枚舉時判斷這個答案是否可行。但是，二分並不是在所有情況下都是可用的，使用二分需要滿足兩個條件:
-
有上下界
-
區間有單調性
二分答案應該是在一個單調閉區間上進行的。也就是說，二分答案最後得到的答案應該是一個確定值，而不是像搜索那樣會出現多解。二分一般用來解決最優解問題。剛纔我們說單調性，那麼這個單調性應該體現在哪裡呢？
可以這樣想，在一個區間上，有很多數，這些數可能是我們這些問題的解，換句話說，這裡有很多不合法的解，也有很多合法的解。我們只考慮合法解，並稱之為可行解。考慮所有可行解，我們肯定是要從這些可行解中找到一個最好的作為我們的答案， 這個答案我們稱之為最優解。
最優解一定可行，但可行解不一定最優。我們假設整個序列具有單調性，且一個數x為可行解，那麼一般的，所有的 \(x'(x'<x)\) 都是可行解。並且，如果有一個數y是非法解，那麼一般的，所有的 \(y'(y'>y)\) 都是非法解。
那麼什麼時候適用二分答案呢？註意到題面：使得選手們在比賽過程中的最短跳躍距離儘可能長。如果題目規定了有“最大值最小”或者“最小值最大”的東西，那麼這個東西應該就滿足二分答案的有界性（顯然）和單調性（能看出來）。
所以（快點）上代碼吧。。。
#include <bits/stdc++.h>
using namespace std;
int n,m,a[100010],l,r;
int f(int x)
{
int ret=0,last=0;
for(int i=1;i<=n;i++)
{
if(last+a[i]<=x)
{
last+=a[i];
}
else{
ret++;
last=a[i];
}
}
return ret;
}
int main()
{
cin >> n >> m;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
for(int i=1;i<=n;i++)
{
l=max(l,a[i]);
r+=a[i];
}
while(l<r)
{
int mid=(l+r)/2;
if(f(mid)>=m)
{
l=mid+1;
}
else{
r=mid;
}
}
cout << l;
return 0;
}
本文來自小默的博客，轉載請註明原文鏈接：https://www.cnblogs.com/momotrace/p/p1182.html
