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
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; } |