Luogu4343 [SHOI2015]自动刷题机

发布于 2019-09-19  189 次阅读


题意

​ 一个自动AC机在某秒结束的时候写了 $xi行代码,这个自动AC机会在写完n行代码以后自动提交并AC此题。现在不知道这个代码长度n,但已知已经AC了k道题,请你求出n{min}n_{max}$

题解

​ 先简单观察题目,发现数据范围是 l \leq 10^5l是总共的秒数),暴力枚举显然会T,所以正解复杂度猜测是O(n\ log \ n)

​ 考虑二分答案这个代码长度n,判断一个答案是否可行可以每次累加每秒结束时的代码长度,如果超过我们二分出的 n,便让题目计数器+1,判断题目计数器与给出的AC题目数比较即可。

​ 最终只需二分两次分别求最大最小值即可。

​ 注意代码注释部分的小细节不同。(记得开long\ long)

Code

好像函数名的最大最小写反了嘤嘤嘤.....

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 100000 + 5;
const long long inf = 0x7f7f7f7f7f7f7f;

#define int long long

int n, k;
int code[SIZE];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline int Judge(int x)
{
    int sum = 0, flag = 0;
    for (int i = 1; i <= n; i++) {
        sum += code[i];
        if (sum >= x) flag++, sum = 0;
        sum = std::max(sum, (int) 0);
    }
    return flag;
}

inline int Binary_Max(int Left, int Right)
{   
    int Mid = 0, ans = -1, flag = 0;
    while (Left <= Right) {
        Mid = (Left + Right) >> 1;
        flag = Judge(Mid);
        if (flag > k) Left = Mid + 1;
        else {
            Right = Mid - 1;
            if (flag == k) ans = Mid; //此处不同自行思考
        }
    }
    return ans;
}

inline int Binary_Min(int Left, int Right)
{
    int Mid = 0, ans = -1, flag = 0;
    while (Left <= Right) {
        Mid = (Left + Right) >> 1;
        flag = Judge(Mid);
        if (flag >= k) {
            Left = Mid + 1;
            if (flag == k) ans = Mid; //此处不同
        }
        else Right = Mid - 1;
    }
    return ans;
}

signed main()
{
    n = read(), k = read();
    for (int i = 1; i <= n; i++) code[i] = read();
    int Max = Binary_Max(1, inf), Min = Binary_Min(1, inf);
    if (Min != -1 ) std::cout << Max << " " << Min;
    else printf("-1");
    return 0;
}

朴实沉毅