洛谷 P1182 数列分段 Section II_给定一个长度为的数列。你需要将数列分成若干互不重叠的区间。 使得 记那么一个划

题目
P1182 数列分段

题目描述
对于给定的一个长度为N的正整数数列 1∼N，现要将其分成 MM（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 行包含两个正整数 N,M。

第 2 行包含 N 个空格隔开的非负整数 A i，含义如题目所述。

输出格式
一个正整数，即每段和最大值最小为多少。

分析

• 二分
  二分法查找符合条件的数，前缀和做铺垫，l为最大的数，r为所有的和数的和。

void search() { //标准二分过程 
  while (l <= r) {
    mid = (l+r)/2;
    //cout<<l<<" "<<r<<" "<<mid<<endl;
    if (judge(mid)) ans = mid, r = mid-1; //如果可以，就存结果，范围前移
    else l = mid+1; //如果不行，就范围后移，
  }
}
1
2
3
4
5
6
7
8

• 判断
  这里的judge函数其实意思就是其中一段小于x就再加，大了就另起一个区间。其中这题的重点就是r往前移找出最小的满足条件的。

bool judge(int x) { //x最大和
  int i = 0, j = 1, k = 0; // i下标 j区间数
  while (i < n) {
    if ((k + a[i+1]) <= x) k += a[++i];//加上当前的和，没超过就加上
    else k = a[++i], j++;//超过了 就标记一个新区间
  }
  return j <= m;
}
1
2
3
4
5
6
7
8

• 前缀和

  for (int i = 1; i <= n; i++) { l为最大的数，r为所有的和数的和
    cin >> a[i];
    r += a[i];
    l = max(a[i], l); //左端是a[i]最大值
  }
1
2
3
4
5

完整代码

#include<bits/stdc++.h>
using namespace std;
int n, m;
int a[100010];
int l, r, mid, ans;//ans和

bool judge(int x) { //x最大和
  int i = 0, j = 1, k = 0; // i下标 j区间数
  while (i < n) {
    if ((k + a[i+1]) <= x) k += a[++i];//加上当前的和，没超过就加上
    else k = a[++i], j++;//超过了 就标记一个新区间
  }
  return j <= m;
}
void search() { //标准二分过程 
  while (l <= r) {
    mid = (l+r)/2;
    //cout<<l<<" "<<r<<" "<<mid<<endl;
    if (judge(mid)) ans = mid, r = mid-1; //如果可以，就存结果，范围前移
    else l = mid+1; //如果不行，就范围后移，
  }
}
int main(){
  cin >> n >> m;
  for (int i = 1; i <= n; i++) { l为最大的数，r为所有的和
    cin >> a[i];
    r += a[i];
    l = max(a[i], l); //左端是a[i]最大值
  }
  search();
  cout << ans;
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

ending ┗( ▔, ▔ )┛