首页 > 代码库 > BZOJ1367 [Baltic2004]sequence
BZOJ1367 [Baltic2004]sequence
现学的左偏树。。。这可是道可并堆的好题目。
首先我们考虑z不减的情况：
我们发现对于一个区间[l, r]，里面是递增的，则对于此区间最优解为z[i] = t[i]；
如果里面是递减的，z[l] = z[l + 1] = ... = z[r] = 这段数的中位数，不妨叫做w。（此处我们定义中位数为第(r - l + 1) / 2大的数，因为这并不影响结果）
而其实递增可以转化为每一段只有一个点，就等价于递减了。
那么我们把原数列分段，每段都是递减的，而每一段的z都是那段的中位数w。这样就找到了最优解。（证略）
这样就有了解法：
(1)新加入一个数至数列末端，先把它当成单独一段
(2)每次看最后一段的w[tot]和前一段的w[tot - 1]，若w[tot] < w[tot - 1]，则说明合并可以更优，合并这两段。
(3)最后计算ans
这之中还有一个问题：z[i]不是不减而是递增。有个巧妙地办法：让z[i]（新） = z[i]（老） - i即可，这样就保证了z的递增性质。
1 /************************************************************** 2 Problem: 1367 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:5284 ms 7 Memory:59400 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <cstring>12 #include <algorithm>13 14 using namespace std;15 const int N = 1500000;16 17 struct heap{18 int v, l, r, dep; 19 }h[N];20 int l[N], r[N], cnt[N], num[N], root[N];21 int z[N];22 int n, tot, Cnt;23 24 inline int read(){25 int x = 0, sgn = 1;26 char ch = getchar();27 while (ch < ‘0‘ || ch > ‘9‘){28 if (ch == ‘-‘) sgn = -1;29 ch = getchar();30 }31 while (ch >= ‘0‘ && ch <= ‘9‘){32 x = x * 10 + ch - ‘0‘;33 ch = getchar();34 }35 return sgn * x;36 }37 38 int new_heap(int x){39 h[++Cnt].v = x;40 h[Cnt].l = h[Cnt].r = h[Cnt].dep = 0;41 return Cnt;42 }43 44 int Merge(int x, int y){45 if (!x || !y) return x + y;46 if (h[x].v < h[y].v)47 swap(x, y);48 h[x].r = Merge(h[x].r, y);49 if (h[h[x].l].dep < h[h[x].r].dep)50 swap(h[x].l, h[x].r);51 h[x].dep = h[h[x].r].dep + 1;52 return x;53 }54 55 int Top(int x){56 return h[x].v;57 }58 59 int Pop(int x){60 return Merge(h[x].l, h[x].r);61 }62 63 int main(){64 n = read();65 for (int i = 1; i <= n; ++i)66 z[i] = read() - i;67 68 for (int i = 1; i <= n; ++i){69 ++tot;70 root[tot] = new_heap(z[i]);71 cnt[tot] = 1, num[tot] = 1;72 l[tot] = i, r[tot] = i;73 74 while (tot > 1 && Top(root[tot]) < Top(root[tot - 1])){75 --tot;76 root[tot] = Merge(root[tot], root[tot + 1]);77 num[tot] += num[tot + 1], cnt[tot] += cnt[tot + 1], r[tot] = r[tot + 1];78 for(; cnt[tot] * 2 > num[tot] + 1; --cnt[tot])79 root[tot] = Pop(root[tot]);80 }81 }82 83 long long ans = 0;84 for (int i = 1; i <= tot; ++i)85 for (int j = l[i], w = Top(root[i]); j <= r[i]; ++j)86 ans += abs(z[j] - w);87 printf("%lld\n", ans);88 return 0;89 }
（p.s. 真是写的矬死了。。。越优化又慢，都醉了）
BZOJ1367 [Baltic2004]sequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。