1000ms

Difficulty: 5

所属公司 : 拼多多

时间 :2025年8月17日

算法与标签>二分算法

会员或题库专享

请先，开通会员或购买题库拼多多机考题库，可解锁完整内容。

购买拼多多机考题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（拼多多机考题库），可解锁完整内容。

购买题库开通会员

思路概述

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

二分答案

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

题目内容

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

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