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\)
-
样例输入
|
1 2 3 4 5 6 7 8 |
7 9 4 8 20 14 15 18 |
-
样例输出
|
1 |
13 |
-
样例说明
所求的 \(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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/priority_queue.hpp> #define _abs(_a) ((_a)<0?-(_a):(_a)) #ifdef ONLINE_JUDGE char __B[1<<15],*__S=__B,*__T=__B; #define getchar() (__S==__T&&(__T=(__S=__B)+fread(__B,1,1<<15,stdin),__S==__T)?EOF:*__S++) #pragma GCC optimize(3) #endif inline int getnum() { register char c=0; while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') a=a*10+c-'0',c=getchar(); return a; } int t[1050505],lpos[1050505],rpos[1050505]; __gnu_pbds::priority_queue<int>pq[1000001]; int main() { register int N=getnum(); register int cnt=0; for(register int i=1;i<=N;i++) { t[i]=getnum()-i; pq[++cnt].push(t[i]),lpos[cnt]=rpos[cnt]=i; while(cnt>1 && pq[cnt].top() < pq[cnt-1].top()) { pq[cnt-1].join(pq[cnt]),pq[cnt--].clear(); rpos[cnt]=rpos[cnt+1]; while((int)(pq[cnt].size()<<1) > rpos[cnt]-lpos[cnt]+2) pq[cnt].pop(); } } long long ans=0; for(register int i=1;i<=cnt;i++) for(register int j=lpos[i];j<=rpos[i];j++) ans+=_abs(t[j]-pq[i].top()); printf("%lld\n",ans); return 0; } |