PKUSC2021部分题目简要题解

个人认为的难度排序:D1T1 < D2T1 < D2T2 < D1T2 < D2T3 < D1T3

两天的\(T1\)都是很简单的题,就不说了

D2T2代金券

• 题意简述:有 \(n\) 道菜品，第 \(i\) 道菜品花费 \(a_i\). 可以使用价值 \(1\) 的消费券，初始时没有消费券。
  如果在一道花费 \(a\) 的菜品花费 \(b(b ≤ a)\)张消费券，则实际需要花
  \(a - b\) 元，并在用餐结束后获得 \(? \frac{a-b} {c} ?\) 张消费券。
  \(Q\) 次对序列 \(a_i\) 修改，每次修改结束后询问按照顺序品尝 \(n\) 个菜品
  的最小消费。

\(1 ≤ n, Q ≤ 3 × 10^5, 1 ≤ c ≤ 10^9, 1 ≤ ai ≤ 10^{12}\)

\(solution\)

• 考试的时候只差一步了.....但还是没AC
• 我们考虑这么一个贪心,首先我们注意令\(d_i = a_i \bmod c,b_i = a_i - d_i\),注意到对于任意一个物品,\(d_i\)使用消费券是一定不劣的,而\(b_i\)个物品如果消费券能留到后面就尽量留到后面
• 所以我们有以下这么一个算法,每次购买\(b_i\),然后\(d_i\)个物品能用消费券就尽量用消费券,那么一定会存在一个后缀\(x\),使得\([x+1,n]\)的所有物品都可以使用消费券
• 那么对于\(x\),我们可以直接二分出要买多少个物品
• 如果是朴素的每次修改完遍历复杂度是\(O(n*q\log A)\)的,我考试也只想到这步
• 注意到如果直接用数据结构维护这么一个过程是极其难以维护的,我们考虑继续观察性质,我们考虑一定会存在一个分界点,使得在那个分界点剩余的消费券等于\(0\),后面的都不等于\(0\),那么我们就可以直接维护,且可以发现最优的后缀一定在这个点后面,否则无法全部使用消费券,我们考虑如何找出这个点
• 我们不妨将\(b_i,d_i\)看成括号匹配,那么问题就比较明朗了,我们令\(s_i = s_{i-1} + b_{i-1} + d_i\),那么\(s_i\)严格最小(若有多个最小点取最右边的)的点就是分界点(这个点消费券一定为\(0\),又因为后面的点都比它大,所以都不为\(0\))
• 这个可以用线段树来维护,在找出这个分界点之后,我们可以直接计算前面使用了多少个消费券(因为为\(0\),所以前面所有产生的消费券都比使用了,即\(d_i\)的前缀和),后面的消费券(因为每次都有盈余,可以直接加加减减),那么我们又可以通过二分来得到\(x\)这个点,注意到\(x\)一定是满足以下条件最左边的点.
• 至\(x\)的消费券不够后面用
• 至\(x+1\)的消费券够后面用
• 又因为由于\(x\)在分界点之后,消费券还剩多少可以直接计算,线段树上二分即可
• 时间复杂度\(O((n + q) (\log A + \log n))\)

原文：https://www.cnblogs.com/y-dove/p/14779565.html