追忆 NOIPro max

我常常追忆过去。

生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云，这使我忆起那段往事……

很久很久以前，有个叫小 R 的人爱吃糖。

有一天，小 R 把我带到小 X 的糖果店，指着店门口诡异的促销策略并跟我说：“只要你用 $m$ 元买到最多的糖果，我就和你在一起。”

~这是什么新型旮旯 game~

我略作沉吟，不出 $20min$ 便给出了正确解法，小 R 看了看我的做法，轻声说：“你果然用了贪心。可我不喜欢贪心的人——无论是在算法里，还是在感情中。”

说罢，ta 转身离去，留下我怔在原地，手中仿佛还握着那袋并不存在的糖。

又是一天，小 R 将我约出，还是熟悉的糖果店，这一次，ta 说：“现在恰逢清仓大甩卖，每颗糖果都以 $1$ 元或 $2$ 元售出，为了最大程度地满足我的心（bian）理（tai）需求，我希望我花 $m$ 元买到的糖果原价之和最大，设第 $i$ 颗糖果的清仓价格为 $w_i \in \{1,2\}$ 元，并定义性价比为原价与清仓价格的比值，即 $\frac{a_i}{w_i}$。采用以下购买策略：将所有糖果按照性价比从大到小排序，然后依次考虑每一颗糖果。具体地，若我在考虑第 $i$ 颗糖果时剩余的钱至少为 $w_i$ 元，则我会购买这颗糖果；否则我会跳过这颗糖果，继续考虑下一颗。特别地，若存在两颗糖果的性价比相同，则我会先考虑原价较高的糖果；若存在两颗糖果的性价比与原价均相同，则我会先考虑编号较小的糖果，我们认为上文的 $i\in[1,n]\cap\mathbb{Z}$ 。那么我的策略是不是无懈可击？”

ta 水灵灵的眼睛眨巴着，透露出一丝俏皮。

我略作思考，答道：“不对，如果依你的策略进行购买，可能出现前一个价格为 $1$ 的糖果 $i$ 购买后不得不放弃价格为 $2$ 的糖果 $j$，之后买下价格为 $1$ 的糖果 $k$ （也可能不存在这个 $k$）后结束反而不如只买糖果 $j$ 怎么办？”

ta 的脸涨的通红，作出生气的样子：“我不信，除非你说出 $2^{n}$ 种可能价格中有多少种情况会使得我的策略算出答案不够优？”

我支支吾吾站在那边思考了 $4h$，小 R 自然是离我远去，凄凉的风拍打在我脸上，看着树枝上一个个 $mex$ 我的心中不尽凄凉。

下一次见到小 R 时，ta 已和小 X 在一起了，那一刻我才明白，我不过是他与她故事之外的一个过客……

这个赛季不明不白结束了。

我该在哪里停留？我问我自己。

（idea by self, 润色 by ai）

我可能该请高人了。

以及这是重构后的游记，第一版因为暴戾语言投不上去 awa 。

尾：死磕 T2 喜提 $100+0+0+0=100$