上午 NOIP模拟赛
A
猜了结论。
一个一个数做。当前这个数插进去的时候，设前驱为pre[i]，后继为nxt[i]。
设x = max(a[pre[i]], a[nxt[i]])，y = min(a[pre[i]], a[nxt[i]])。
则：
当a[i] > x时，ans += a[i] - x;
当a[i] < y时，ans += y - a[i];
否则ans不变。
不变还是好理解的，因为原来的方案里面x加到y的过程把a[i]包含了。
其他时候感觉可以理解成把a[i]和x或者y先并成一个数，再按照原来的方案操作。
考试的时候一下就想到了这个结论，但是数组开小了，还是写太快了/qd。100 -> 40，输。
B
考试的时候写了个假的dp，输。
考试后学习了@QAQfj5的超绝单调队列。
考虑维护一个冰箱。
把所有能选的棒冰都尽量塞进冰箱里。
对于当前的i，如果吃到的棒冰是在位置j买的。那么每根棒冰在j买完再保存到i耗费的代价就是p[j] + (i - j) * m。
显然要选这个代价最小的位置来买棒冰。把i * m提出来，剩下的就是p[j] - j * m。把这个丢进单调队列里面维护，就可以得到代价最小的j。
如果冰箱容量不限。显然每次取队头就可以。
考虑怎么维护冰箱的容量。
考虑对于每一天的棒冰，在冰箱里存它能买的最大个数。
具体实现就是在单调队列里塞二元组。
{x, y}表示在位置x买的棒冰，最多还存着y根。
每次对于位置i，先从队头开始吃存着的棒冰，如果存货不够再新买来吃。
最后用第i个位置买的棒冰填满冰箱。此时填的个数就是维护出了位置i最多存几根棒冰在冰箱里。
按照思路就能把代码实现。非常好贪心。
