AtCoder题解｜ABC 319 D - Minimum Width

题目信息 📚

【题目描述】

Takahashi is displaying a sentence with $N$ words in a window. All words have the same height, and the width of the $i$-th word $(1 \leq i \leq N)$ is $L_i$.

The words are displayed in the window separated by a space of width $1$. More precisely, when the sentence is displayed in a window of width $W$, the following conditions are satisfied:

The sentence is divided into several lines.
The first word is displayed at the beginning of the top line.
The $i$-th word $(2 \leq i \leq N)$ is displayed either with a gap of $1$ after the $(i-1)$-th word, or at the beginning of the line below the line containing the $(i-1)$-th word. It will not be displayed anywhere else.
The width of each line does not exceed $W$. Here, the width of a line refers to the distance from the left end of the leftmost word to the right end of the rightmost word.

When Takahashi displayed the sentence in the window, the sentence fit into $M$ or fewer lines. Find the minimum possible width of the window.

【输入】

The input is given from Standard Input in the following format:

$N$ $M$

$L_1$ $L_2$ $\dots$ $L_N$

【输出】

Print the answer in one line.

【数据范围】

$1 \leq M \leq N \leq 2 \times 10^5$
$1 \leq L_i \leq 10^9$ $(1 \leq i \leq N)$

All input values are integers.

【输入样例1】

13 3
9 5 2 7 1 8 8 2 1 5 2 3 6

【输出样例1】

【输入样例2】

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

【输出样例2】

10000000009

【输入样例3】

30 8
8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32 60

【输出样例3】

【题目来源】

https://atcoder.jp/contests/abc319/tasks/abc319_d

题目解析 🍉

【题目分析】

经典二分答案。

【C++代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL a[N], n, m, sum = 0;

// 判断宽度为x的情况下，能否满足条件
bool check(LL x) {
    LL cur = 0;
    LL lines = 1;
    int i = 1;
    while (i <= n) {
        if (x < a[i]) return false;
        cur += a[i];
        if (cur == x) {
            if (i != n) lines++, cur = 0;
            i++;
        } else if (cur < x) cur++, i++;  // 添加一个末尾空格
        else if (cur > x) lines++, cur = 0;
    }
    return lines <= m;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 读入数据并且计算最大可能宽度
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    sum += (n - 1);

    // 二分答案
    LL l = 1, r = sum;
    while (l < r) {
        LL mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << endl;

    return 0;
}