思路概述

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

二分答案

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

题目内容

多多最近迷上了一款闯关游戏，游戏中有$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$

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写