AT-ABC-319D题解

robertuu · 2023-09-10 13:17:37 · 题解

题目传送门

很简单的二分（代码比 C 好写多了）！

很显然，可以发现，当窗口长度变长时，使用的行数肯定不会变多（可以用自己的电脑中的 word 试一下），具有单调性！

可以使用二分，二分的范围是 [1,2 \times 10^{14}]，每次二分检查行数（只需要扫一遍即可，扫描时有地方就占用，没地方新开一行）是否满足要求并缩小范围即可（注意题目求的是满足要求的最小长度）。

AC code:

#include<bits/stdc++.h>
using namespace std;
int n;
long long a[200001];
int check(long long x)
{
    int cnt = 1; // 行数
    long long d = x+1; // 当前行剩余位置（为了避免第一个无空格的分类讨论就加了1）
    for(int i = 1;i <= n;i++)
    {
        if(d >= a[i]+1) d -= a[i]+1; // 注意要有空格
        else
        {
            cnt++;
            if(x < a[i]) return 2e9;
            d = x-a[i];
        }
    }
    return cnt;
}
int main()
{
    int k;
    scanf("%d%d",&n,&k);
    for(int i = 1;i <= n;i++) scanf("%lld",&a[i]);
    long long l = 1,r = 1e18;
    while(l < r)
    {
        long long mid = (l+r)/2;
        if(check(mid) <= k) r = mid; // 范围缩小到小于等于mid
        else l = mid+1; // 范围缩小到大于mid
    }
    printf("%lld",l);
    return 0;
}