思路概述

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

P3396.第3题-闯关游戏

1000ms

Difficulty: 5

所属公司 : 拼多多

算法与标签>二分算法

多多最近迷上了一款闯关游戏，游戏中有 $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$ 个关卡的得分和难度

一个整数表示答案

输入

输出

说明

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

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

输入

预期输出（选填）