B4433 [语言月赛 202511] 天上掉下个哈基米

览遍千秋 · 2025-11-24 07:33:56 · 题解

来源

2025 年 11 月语言月赛，由洛谷网校提供。

考察一维数组。

欢迎报名洛谷网校，报名课程可以获得对应组别的知识点讲解与答疑服务，期待和大家一起进步！点击图片即可报名。

:::align{center} :::

文字题解

给出压缩后的结果，v_i,l_i 表示压缩结果的一项，询问原数列中第 x 个数是什么。

考虑压缩后的结果序列 (v_1, l_1), (v_2,l_2), \cdots, (v_n, l_n)，原数列中的第 x 个数将属于满足下列条件的 (v_i, l_i)：

• l_1+l_2+\cdots+l_{i-1}<x
• l_1+l_2+\cdots+l_i\ge x

通过循环枚举 i，可以找到答案。

时间复杂度为 O(nT)。