自动搬运

查看原文

来自洛谷，原作者为

	wheneveright 必修课选逃，选修课必逃！

搬运于2025-08-24 21:56:19，当前版本为作者最后更新于2021-05-13 14:43:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析

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

二分答案的题目一般都是对于答案决策有单调性题目，例如这道题，当 $\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;
}