题解 P4085 [USACO17DEC]Haybale Feast G

· · 题解

分析

这是一道二分答案的板子题。

二分答案的题目一般都是对于答案决策有单调性题目，例如这道题，当 \max (s) 大的时候连续的一段可以选取的和一定大于等于 \max (s) 小的，所以具有单调性质，可以用二分答案的方法解决这道题。

因为要求是求 \max (s) 的最小值使得连续一段 F 序列的和大于等于 M，求的是 \max (s)，所以可以考虑二分 \max (s)，然后 O(n) check 看看有没有一段连续一段可以选择的 F 满足条件。

然后记得开 long long 就好了。时间复杂度 O(n \log \max \{S\})。

代码

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

int N;
long long F[1000005], S[1000005], M, sum, L, R, mid, res;

bool check (int maxs) {
    sum = 0;
    for (int i = 1; i <= N; i++) {
        // 如果 S 不满足条件就清零，否则刷最大值
        if (S[i] > maxs) sum = 0;
        else sum += F[i];
        if (sum >= M) return true;
    }
    return false;
}

int main () {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> F[i] >> S[i];
        R = max (R, S[i]);
    }   L = 1;
    while (L <= R) check (mid = ((L + R) >> 1)) ? R = mid - 1, res = mid : L = mid + 1;
    // 二分答案板子
    printf ("%lld\n", res);
    return 0;
}