Problem
题目简述
设序列 \(a\) ,并且是单调递增的。设 \(a\) 当前长度为 \(l\),你要对 \(a\) 作差分,即令 \(b_i = a_{i+1} - a_i(1\le i < l)\),然后使 \(b\) 数组保持单调递增。
一直持续操作,直到 \(a\) 数组中只有一个元素 \(x\),输出 \(x\)。
暴力 \(\to\) 优化
暴力的话,就是纯模拟。
时间复杂度:\(O(n^2)\),本题 \(1 \le n \le 10^5\),时间复杂度达到了惊人的 \(10^{10}\)。
考虑如何优化。
我们得出一个结论:差分的时候,一定会有 \(0\) 出现,而 \(+0/-0\) 都对结果造不成影响,所以我们可以排除 \(0\) 的存在。
但是,我们经过模拟样例发现,\(0\) 在一定程度上是会对差分结果造成影响的。那我们改如何处理呢?
定义变量 \(x\),记录之前删没删过 \(0\)。
每次差分前,如果 \(x > 0\),表示删除过 \(0\)。
此时,我们可以先将 \(a_1\) 加入 \(b\) 中,这样下次差分就会产生出一个 \(0\)。
这时我们可以将 \(x\) 减 \(1\),因为如果一直加反而会导致结果的错误。
代码就不贴了,实现比较简单。