P4343 [SHOI2015]自动刷题机

找最大值：二分到一个n的值t，然后根据日志检查在t的情况下能切几题，如果满足切的题目数>=k，那么所有比t小的值都能够使得切题数>=k，此时可能可以找到n的最大值，因为如果不存在一个t能使切题数正好是k的话，找到的值是最大的能够使切题数>k的值

找最小值：二分到一个n的值t，如果满足切的题目数<=k，那么所有比t大的值都能够使得切题数<=k，此时可能可以找到n的最小值，因为如果不存在一个t能使切题数正好是k的话，找到的值是最小的能够使切题数<=k的值

复杂度：(O(l log N)), 其中N是n的二分范围大小，一开始取得范围很大((log N)大约是60的样子)，T掉了，后来把范围缩小成([1, 2^{41}]),就是(log N = 41)过了

另外还需要注意的就是，先找最小值，找到以后需要特判一下二分出来的最小值能不能让切题数正好是k，不能就直接输出-1

#include<iostream>
#include<cstring>
using namespace std;

const int N = 100010;

#define LL long long

LL a[N];
int ll, k;

LL check(LL x){
    LL cnt = 0;
    int res = 0;
    for(int i = 0; i < ll; i ++){
        cnt = max(cnt + a[i], (LL) 0);
        if(cnt >= x) res ++, cnt = 0;
    }
    return res;
}

int main(){
    cin >> ll >> k;
    for(int i = 0; i < ll; i ++) cin >> a[i];
    
    LL l = 1, r = (LL) 1 << 41;
    while(l < r){
        LL mid = l + r >> 1;
        if(check(mid) <= k) r = mid; // 如果切题的个数满足<=k
        else l = mid + 1;
    }
    
    if(check(l) != k){
        puts("-1");
        return 0;
    }
    
    cout << l << ' ';
    
    l = 1, r = (LL) 1 << 41;
    while(l < r){
        LL mid = l + r + 1 >> 1;
        if(check(mid) >= k) l = mid;
        else r = mid - 1;
    }
    
    cout << l;
    
    return 0;   
}