题解 P4343 【[SHOI2015]自动刷题机】

Ofnoname · 2019-10-13 00:01:56 · 题解

肺都给气炸了，二分答案对来说实在是太难缠了。

容易发现，对于给定的序列，n越大能过的题是越少的，所以可以二分来求刚好过k道题的左右边界。

若mid大于k,即做得太多了，就将l右移。

若mid小于k,即做得太少了，就将r左移。

求左边界，需要在mid等于k时将r左移，求右边界时则需将l右移。这个很好理解。

印象里二分写法极多，但现在普遍应用l<=r, l=mid+1, r=mid-1这个版本了，虽然要多记录一个ans，但是却在单调增单调减时都能工作，并且可以轻松应对无解的情况。

注意这种写法l应设为1，r设为无穷大即可。

#include <bits/stdc++.h>
#define MAX (100000 + 7)
#define long long long
using namespace std;

int N, k, a[MAX];
long l, r, ans1 = -1, ans2 = -1;

long work(long im)
{
    int ans = 0; long sum = 0;
    for (int i = 1; i <= N; i++)
    {
        sum = max(sum + a[i], 0ll);
        if (sum >= im) sum = 0, ans++;
    }return ans;
}

int main()
{
    scanf("%d%d", &N, &k);
    for (int i = 1; i <= N; i++)
        scanf("%d", a + i);
    l = 1, r = 1e18;//注意l应设为1 
    while (l <= r)
    {
        long mid = (l + r) >> 1;
        if (work(mid) <= k)
        {
            r = mid - 1;
            if (work(mid) == k) ans1 = mid;//注意符合条件才更新答案 
        }
        else l = mid + 1;
    }

    l = 1, r = 1e18;//注意l应设为1 
    while (l <= r)
    {
        long mid = (l + r) >> 1;
        if (work(mid) >= k)
        {
            l = mid + 1;
            if (work(mid) == k) ans2 = mid;//注意符合条件才更新答案 
        }
        else r = mid - 1;
    }
    if (ans1 == -1) puts("-1");
    else printf("%lld %lld\n", ans1, ans2);
}