「SHOI2015」自动刷题机-二分

题目描述

SHTSC发明了一种自动刷题机，它刷题的方式非常简单：首先会瞬间得出题目的正确做法，然后开始写程序。每秒，自动刷题机的代码生成模块会有两种可能的结果：

1.写了\(x\)行代码

2.心情不好，删掉了之前写的\(y\)行代码。（如果\(y\)大于当前代码长度则相当于全部删除。）

对于一个 OJ，存在某个固定的长度\(n>0\)，一旦自动刷题机在某秒结束时积累了大于等于\(n\)行的代码，它就会自动提交并 AC 此题，然后新建一个文件（即弃置之前的所有代码）并开始写下一题。SHTSC 在某个 OJ 上跑了一天的自动刷题机，得到了很多条关于写代码的日志信息。他突然发现自己没有记录这个 OJ 的\(n\)究竟是多少。所幸他通过自己在 OJ 上的 Rank 知道了自动刷题机一共切了\(k\)道题，希望你计算\(n\)可能的最小值和最大值。

Links

Luogu P4343

Solution

本题显而易见的就是一道基本的二分，用两次二分，一次求最小值，一次求最大值，就可以了

Code

#include<bits/stdc++.h>
#include<climits>
const int maxn = 100001;
using namespace std;

int code[maxn];
int l,k;

int check(long long len){ //若长度为len时提交则可以AC的题目数量
    long long sum = 0;
    int ac = 0;
    for(int i = 1; i <= l; i++){
        sum += code[i];
        if(sum < 0){ sum = 0;continue;}
        else if(sum >= len) ++ac,sum = 0;
    }
    return ac;
}

long long BinSearch(){ //二分查找最大
    long long left = 0,right = LLONG_MAX;
    long long ans = -1;
    long long mid;
    while(left + 1 < right){
        mid = (left + right) / 2;
        int len = check(mid); 
        if(len == k) ans = mid;
        if(len >= k) left = mid;
        else right = mid;
    }
    return ans;
}

int main(){
    scanf("%d%d",&l,&k);
    for(int i = 1; i <= l; i++){
        scanf("%d",&code[i]);
    }
    long long max = BinSearch(); //二分求最大值
    if(max == -1){ //如果最大值为-1，则无解，直接输出-1结束程序
        printf("-1");
        return 0;
    }
    k++;
    long long min = BinSearch() + 1;//二分求最小值(即切掉k+1道题时的最大值+1)
    if(min == 0) min++;
    printf("%lld %lld",min,max);  
    return 0;
}