洛谷P4343 自动刷题机

url: https://www.luogu.com.cn/problem/P4343

tag:
二分，模拟

思路：
思路比较简单，根据题目可以知道当n越小时切出来的题目数量越多，根据这个来二分。分别二分出一个最小值和一个最大值。这道题是细节比较 恶心（bushi 多，需要注意的点比较多。第一个是二分的范围，题目只有一个xi的范围是1e-9到1e9，经测试，r开到1e9范围比较小，看了题解之后发现需要开到1e18.然后这里就有一个问题，因为超过了1e9所以变量不能放到main()函数中，只能放到外面当全局变量。然后如果是mid要用long long类型，记得check函数的函数签名中变量的类型也要是long long。第二个细节是l要从1开始，不能从0开始。第三个细节是，题目没有保证说如果其中一个答案比如最小值存在，另外一个答案就会存在，所以对于最小值和最大值都要进行验证。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
long long n, k, l ,r;
long long p[N];

long long check (long long x)
{
    long long sum = 0, cnt = 0;
    for (int i = 0; i < n; i ++)
    {
        if (p[i] > 0) sum += p[i];
        else sum = max((long long)0, sum + p[i]);
        if (sum >= x)
        {
            sum = 0;
            cnt ++;
        }
    }
    return cnt;
}
int main()
{
    scanf("%lld%lld", &n, &k);
    for (int i = 0; i < n; i ++) scanf("%lld", &p[i]);
    l = 1, r = 1e18;

    while (l < r)
    {
        long long mid = (l + r) >> 1;
        if (check(mid) <= k) r = mid;
        else l = mid + 1;
    }
    long long tmp;
    if (check(l) != k)
    {
        cout << -1 ;
        return 0;
    }
    else tmp = l;
    l = 1, r = 1e18;
    while (l < r)
    {
        long long mid = (l + r + 1) >> 1;
        if (check(mid) >= k) l = mid;
        else r = mid - 1;
    }
    if (check(l) != k)
    {
        cout << -1 ;
        return 0;
    }
    else cout << tmp << ' ' << l;
    return 0;
}