[数据结构与算法]LibreOJ #2036. 「SHOI2015」自动刷题机

题目链接：https://loj.ac/p/2036

题面：

?

思路：二分查找，二分[1, 1e17]的区间，用二分的方法查找出最小情况和最大情况，如果最小情况大于最大情况就输出-1，否则就输出

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
#define N 100005
int a[N];
int main(){
    ios::sync_with_stdio(false);
    int n, k;
    while(cin >> n >> k){
        for(int i = 1; i <= n; i++){
            cin >> a[i];
        }
        ll l = 1, r = 1e17;
        while(l <= r){
            ll mid = (l + r) / 2;
            ll sum = 0;
            ll ans = 0;
            for(int i = 1; i <= n; i++){
                sum += a[i];
                sum = max((ll)0, sum);
                if(sum >= mid){
                    ans++;
                    sum = 0;
                }
            }
            if(ans > k){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }

        ll c = l;
        l = 1, r = 1e17;
        while(l <= r){
            ll mid = (l + r) / 2;
            ll sum = 0, ans = 0;
            for(int i = 1; i <= n; i++){
                sum += a[i];
                sum = max((ll)0, sum);
                if(sum >= mid){
                    ans++;
                    sum = 0;
                }
            }
            if(ans >= k){
                l = mid  + 1;
            }else{
                r = mid - 1;
            }
        }
        ll d = r;
        if(c > d){
            cout << -1 << endl;
        }else{
            cout << c << " " << d << endl;
        }

    }
    return 0;
}