Codeforces Round #371 & HihoCoder1529【玄学】

时间:2022-06-08 21:43:08
时间限制:40000ms
单点时限:2000ms
内存限制:256MB

描述

给定一个长度为 n 的非负整数序列 a[1..n]。

你每次可以花费 1 的代价给某个 a[i] 加1或者减1。

求最少需要多少代价能将这个序列变成一个不上升序列。

输入

第一行一个正整数 n

接下来 n 行每行一个非负整数,第 i 行表示 a[i]。

1 ≤ n ≤ 500000

0 < a[i] ≤ 109

输出

一个非负整数,表示答案。

样例解释

[5,3,4,5] -> [5,4,4,4]

样例输入
4
5
3
4
5
样例输出
2

玄学,堆???

想了两节课,无果。。。。。。。。。。。。

http://codeforces.com/blog/entry/47094?#comment-315161