YZOJ P3933 [Baltic2004]sequence

YZOJ P3933 [Baltic2004]sequence

时间限制:1000MS      内存限制:65536KB

难度:\(6.0\)

  • 题目描述

给定一个序列 \(t_1,t_2,\cdots,t_n\),求一个递增序列 \(z_1<z_2<\cdots<z_n\),使得 \(R=\sum\limits_{i=1}^{n}{\left|t_i-z_i\right|}\) 的值最小。

本题中,我们只需要求出这个最小的 \(R\) 值。

  • 输入格式

第一行为一个正整数 \(n\)

第二行到第 \(n+1\) 行,每行一个整数,第 \(k+1\) 行为 \(t_k\)

  • 输出格式

一个整数 \(R\)

  • 样例输入

  • 样例输出

  • 样例说明

所求的 \(z\) 序列为 \(6,7,8,13,14,15,18\),\(R=13\)

  • 数据规模与约定

对于 \(100\%\) 的数据,\(1 \leq n \leq 10^6\),\(1 \leq t_i \leq 2\times 10^9\) 。

 

 

Source: BZOJ 1367


 

 

 

尝试弱化条件,考虑找到单调不升的 \(z\) 。

经过 推理 猜测和验证,可以发现对于 \(a_i\) 单调不降的某段区间, \(z_j\) 等于 \(a_i\) 使得答案最小。

进而,可以发现对于 \(a_i\) 单调不升的某段区间,\(z_j\) 等于 \(a_{mid}\) 使得答案最小(\(a_{mid}\) 表示这段区间的中位数)。

问题转化为,要把 \(a\) 分割成连续的几段区间,使得每段区间的中位数单调不降

维护区间中位数可以用一个堆,使堆满足 \({元素个数} = \lfloor\frac{\large{区间长度}}{2}\rfloor\) , 堆顶即是中位数(取不取平均值答案相同) 。

注意到为了使中位数单调不降,可能会把当前堆与上一个区间的堆合并,所以使用 pb_ds 配对堆 左偏树维护。

还有,要求单调上升的 \(z\) ,只需要把 \(a_i\) 修改为 \(a_i-i\) 即可。

https://wenku.baidu.com/view/20e9ff18964bcf84b9d57ba1.html

(我 pb_ds 做错了什么www

 

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注