思路概述

给定 $N$ 个关卡，每关有得分 $S_i$ 和难度 $D_i$。需找一段连续关卡，使得得分和 $\ge T$，并最小化这段关卡中的最大难度。 典型的 最小化最大值 + 连续区间判定，用 二分答案 + 滑动窗口 即可。

二分答案

• 将所有难度唯一化后升序排列，或直接在区间 $[1,10^9]$ 上二分。
• 判断函数 check(mid)：只考虑难度 $\le mid$ 的关卡，能否找到得分和 $\ge T$ 的连续段。

判断函数

对难度 $\le mid$ 的连续块用滑动窗口累积得分：

1. 初始化 sum=0。

2. 逐关卡遍历

   • 若 D_i>mid，窗口被打断，sum 归零。
   • 否则 sum+=S_i，若 sum>=T 立即返回 true。

3. 遍历结束仍未成功则返回 false。 复杂度 $O(N)$。

复杂度

• 二分层数 $\log M$，$M\le10^9$（或 $\log N$ 若用去重难度）。
• 单次判断 $O(N)$。
• 总复杂度 $O(N\log N)$，空间 $O(1)$。

代码实现

Python

# 读取输入
import sys

n, T = map(int, sys.stdin.readline().split())
S, D = [], []
for _ in range(n):
    s, d = map(int, sys.stdin.readline().split())
    S.append(s)
    D.append(d)

def ok(limit: int) -> bool:
    """判断最大难度<=limit时是否可行"""
    cur = 0
    for s, d in zip(S, D):
        if d > limit:
            cur = 0          # 窗口被打断
        else:
            cur += s
            if cur >= T:
                return True
    return False

# 二分搜索答案
lo, hi = 1, max(D)
while lo < hi:
    mid = (lo + hi) // 2
    if ok(mid):
        hi = mid
    else:
        lo = mid + 1

print(lo)

Java

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static long T;
    static long[] S;
    static int[] D;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        T = Long.parseLong(st.nextToken());

        S = new long[n];
        D = new int[n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            S[i] = Long.parseLong(st.nextToken());
            D[i] = Integer.parseInt(st.nextToken());
        }

        int lo = 1, hi = Arrays.stream(D).max().getAsInt();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (ok(mid)) hi = mid;
            else lo = mid + 1;
        }
        System.out.println(lo);
    }

    // 判断最大难度<=limit时是否存在得分>=T的连续段
    static boolean ok(int limit) {
        long sum = 0;
        for (int i = 0; i < n; i++) {
            if (D[i] > limit) {
                sum = 0;            // 被打断
            } else {
                sum += S[i];
                if (sum >= T) return true;
            }
        }
        return false;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int INF = 1e9;

int n;
int64 T;
vector<int64> S;
vector<int> D;

bool ok(int lim) {
    int64 sum = 0;
    for (int i = 0; i < n; ++i) {
        if (D[i] > lim) sum = 0;        // 窗口断开
        else {
            sum += S[i];
            if (sum >= T) return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> T)) return 0;
    S.resize(n); D.resize(n);
    for (int i = 0; i < n; ++i) cin >> S[i] >> D[i];

    int lo = 1, hi = *max_element(D.begin(), D.end());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (ok(mid)) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << '\n';
    return 0;
}

题目内容

多多最近迷上了一款闯关游戏，游戏中有$N$个依次排列的关卡,每个关卡都有两个属性:

$1$.通关奖励:完成这个关卡能获得多少积分

$2$.挑战难度:这个关卡有多难通过，用一个正整数表示

现在多多想要选择一段连续的关卡来挑战(比如第$3$关到第$7$关)，这段关卡需要满足:这些关卡的总积分奖励至少要达到目标分数$T$;在满足积分要求的前提下，选中的关卡中最大的难度值要尽可能小

请找出满足条件的一段连续关卡，输出这段关卡的最高难度，题目保证必定有解

输入描述

第一行两个整数$N(1≤N≤100,000)$ 和$T(1<=T<=1e18)$分别表示关卡的数目和目标分数

接下来$N$行，每行两个整数$Si(1≤Si≤1e18)$和 $Di (1<=Di<=1e9)$，分别表示第$i$个关卡的得分和难度

输出描述

一个整数表示答案

样例1

输入

5 10
4 10
6 15
3 5
4 9
3 6

输出

9 

说明

选择关卡$3-5$，总得分为$3+4+3>=$目标分数$10$,难度为$9$

其他满足总得分$>=10$的关卡，最高难度都大于$9$