CF521D Shop 题解

未看题解完成，用时 34min 7s。

对一个位置而言赋值操作肯定最多进行一次，因此考虑直接贪心。注意到一定存在一个最优策略满足对每个位置，其执行的操作的顺序都是（赋值）-（加法）-（乘法），括号代表一个操作可有可无。证明可以简单 Exchange-Argument Trick 处理。

考虑先把所有的赋值操作对每个位置只保留赋值最大的操作，然后将其全部转化成加法操作，然后再把加法操作排序之后全部转化成乘法操作。乘法操作直接贪心选最大的 $m$ 个数执行操作即可。

总时间复杂度为 $O(n\log n)$ 可以轻松通过该题。