题目链接
原始题面
题目描述
对于给定的一个长度为 \(N\) 的正整数数列 \(A_{1\sim N}\), 现要将其分成 \(M\) (\(M\leqslant 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
说明 / 提示
对于 \(20\%\) 的数据，\(N\leqslant 10\).
对于 \(40\%\) 的数据，\(N\leqslant 1000\).
对于 \(100\%\) 的数据，\(1\leqslant N\leqslant 10^5\), \(M\leqslant N\), \(A_i\) 之和不超过 \(10^9\).
解题思路
二分答案
查询区间:
\[
\bigg[\max_{1\leqslant i\leqslant n}\{A_i\},\sum_{i=1}^n A_i\bigg]
\]
另外，注意左端点，如果令其为 0 则会 WA 一个点
时间复杂度
\(O(n\log(r-l))\), 其中 \(l,\ r\) 分别指查询区间左右端点
代码参考
Show code
Luogu_P1182view raw1
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
#include <bits/stdc++.h>
#define _for(i, l, r) for (auto i = (l); i <= (r); ++i)
namespace FastIO {
char buf[1 << 21], buf2[1 << 21], a[20], *p1 = buf, *p2 = buf, hh = '\n';
i64 p, p3 = -1;
i64 getc() {
return p1 == p2 &&
(p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ?
EOF :
*p1++;
}
void read() {}
void print() {}
template <typename T, typename... T2>
void read(T &x, T2 &...oth) {
i64 f = 0;
x = 0;
char ch = getc();
while (!isdigit(ch)) {
if (ch == '-') f = 1;
ch = getc();
}
while (isdigit(ch)) {
x = x * 10 + ch - 48;
ch = getc();
}
if (f) x = -x;
read(oth...);
}
void flush() { fwrite(buf2, 1, p3 + 1, stdout), p3 = -1; }
template <typename T, typename... T2>
void print(T x, T2... oth) {
if (p3 > 1 << 20) flush();
if (x < 0) buf2[++p3] = 45, x = -x;
do { a[++p] = x % 10 + 48; } while (x /= 10);
do { buf2[++p3] = a[p]; } while (--p);
buf2[++p3] = hh;
print(oth...);
}
template <typename T>
void print_h(T x, char h) {
if (p3 > 1 << 20) flush();
if (x < 0) buf2[++p3] = 45, x = -x;
do { a[++p] = x % 10 + 48; } while (x /= 10);
do { buf2[++p3] = a[p]; } while (--p);
buf2[++p3] = h;
}
void putchar(char a) { buf2[++p3] = a; }
}
using FastIO::print;
using FastIO::print_h;
using FastIO::read;
const i64 N = 1e5 + 5;
i64 n, m, a[N];
bool judge(i64 max) {
i64 seg = 0, now_sum = 0;
_for(i, 1, n) {
now_sum += a[i];
if (now_sum >= max) {
++seg;
now_sum = (now_sum > max) ? a[i] : 0;
}
if (seg > m) return 0;
}
if (now_sum) ++seg;
return seg <= m;
}
int main() {
read(n, m);
i64 l = 0, r = 0, mid;
_for(i, 1, n) {
read(a[i]);
r += a[i];
l = std::max(l, a[i]);
}
while (l < r) {
mid = l + (r - l) / 2;
if (judge(mid)) r = mid;
else l = mid + 1;
}
print(r);
ex:
FastIO::flush();
return 0;
}
|