sequence

NC212499. sequence

描述

给定一个序列t1,t2,...,tnt1,t2,...,tn，求一个递增序列z1<z2<...<znz1<z2<...<zn，使得R=|t1−z1|+|t2−z2|+...+|tn−zn|R=|t1−z1|+|t2−z2|+...+|tn−zn|的值最小。本题中，我们只需要求出这个最小的R值。

输入描述

第1行为一个整数n(1<=n<=106)n(1<=n<=106)， 第2行到第n + 1行，每行一个整数，第k + 1行为tk(0<=tk<=2∗109)tk(0<=tk<=2∗109).

输出描述

一个整数R

示例1

输入:

输出:

说明:

所求的Z序列为6, 7, 8, 13, 14, 15, 18.
R=13

上次编辑到这里，代码来自缓存点击恢复默认模板

详情