脚本宝典收集整理的这篇文章主要介绍了洛谷[P1182] 数列分段 Section II，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
对于给定的一个长度为N的正整数数列 A1∼N，现要将其分成 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。
二分查找的经典应用：最大值的最小值。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorIThm> 4 #include <stdio.h> 5 6 using namespace std; 7 8 const int M = 1000000006; 9 int n, k, l, a[200000]; 10 11 inline void read(int & x) 12 { 13 x = 0; 14 int k = 1; 15 char c = getchar(); 16 while (!isdigit(c)) 17 if (c == '-') c = getchar(), k = -1; 18 else c = getchar(); 19 while (isdigit(c)) 20 x = (x << 1) + (x << 3) + (c ^ 48), 21 c = getchar(); 22 x *= k; 23 } 24 25 inline bool check(int p) 26 { 27 int sum = 0, tot = 0; 28 for (int i = 1; i <= n; ++i) 29 { 30 sum += a[i]; 31 if (sum > p) sum = a[i], tot++; 32 } 33 if (sum != 0) ++tot; 34 if (tot <= k) return 1; 35 return 0; 36 } 37 38 int binery_seArch(int l, int r) 39 { 40 if (l == r) return l; 41 int mid = (l + r) >> 1; 42 if (check(mid)) return binery_search(l, mid); 43 else return binery_search(mid + 1, r); 44 } 45 46 int main() 47 { 48 int ms = -1; 49 read(n), read(k); 50 for (int i = 1; i <= n; ++i) 51 read(a[i]), ms = max(ms, a[i]); 52 cout << binery_search(ms, M); 53 return 0; 54 }@H_777_725@
以上是脚本宝典为你收集整理的洛谷[P1182] 数列分段 Section II全部内容，希望文章能够帮你解决洛谷[P1182] 数列分段 Section II所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。