Readme

3048.Earliest-Second-to-Mark-Indices-I

首先要看出这道题存在单调性，肯定时间越多的话，越有机会将所有元素都清零并标记。由此我们考虑尝试二分搜值。二分法的优点是，不用直接求“最优解”，而是转化为判定“可行解”，难度上会小很多。

本题里，我们需要在给定时间s的情况下，问能否将所有元素都清零并标记。对于一个给定的index而言，我们必须在对其“标记”前完成清零，因此我们肯定会将“标记”操作尽量延后，方便腾出更多时间做减一的操作。显然，我们会贪心地将index最后一次出现的时刻做“标记”操作；而如果index出现了不止一次多次，那么除了在最后一次的时刻做“标记”外，其余的时刻都会留作做“减一”操作（但不一定针对nums[idx]）。为了顺利能够在最后一次index出现的时候做标记，我们需要保证之前积累的“减一”操作足够多，能够大于等于nums[idx]即可。于是我们只要顺着index出现的顺序，模拟上述的操作：要么积累“减一”操作count（如果不是最后一个出现），要么进行“标记”操作（如果是最后一次操作）。对于后者，能进行“标记”操作的前提是已经对那个index的数进行多次减一至零，故要求count>=nums[idx].

如果能够顺利地走完changeIndices[1:s]、并且将所有的nums都完成“标记”的话，就说明s秒能够实现目标。