BZOJ 1112: [POI2008]磚塊Klo 平衡樹，思維，枚舉

2019-11-10 16:57:16

字體：大中小

來源：轉載

供稿：網友

Description

N柱磚,希望有連續K柱的高度是一樣的. 你可以選擇以下兩個動作 1:從某柱磚的頂端拿一塊磚出來,丟掉不要了. 2:從倉庫中拿出一塊磚,放到另一柱.倉庫無限大. 現在希望用最小次數的動作完成任務. Input

第一行給出N,K. (1 ≤ k ≤ n ≤ 100000), 下面N行,每行代表這柱磚的高度.0 ≤ hi ≤ 1000000 Output

最小的動作次數 Sample Input 5 3

1 Sample Output 2

解題方法：我們線性掃區間，然后每個區間的中位數肯定是這個區間的選取的高度。搞出這個高度后我們要將這個區間內的所有的數與選取的高度作差取絕對值求和。所以轉化成，我們需要一種數據結構支持刪點，加點，找排名為rnk的數，詢問部分求和。所以上個Treap就好了。至于求和，記個sum，比中位數小的用中位數乘個數減求和，比中位數大的用求和減中位數乘個數。其實就是平衡樹裸題了。代碼如下：

#include <bits/stdc++.h>using namespace std;const int maxn = 100010;typedef long long LL;int n, k;LL h[maxn];int size, root;struct node{ int l, r, rnd; LL siz, v, sum;}tr[maxn];void pushup(int &rt){ tr[rt].siz = tr[tr[rt].l].siz + tr[tr[rt].r].siz + 1; tr[rt].sum = tr[tr[rt].l].sum + tr[tr[rt].r].sum + tr[rt].v;}void lturn(int &rt){ int t=tr[rt].r; tr[rt].r=tr[t].l; tr[t].l=rt; tr[t].siz=tr[rt].siz; pushup(rt); rt=t;}void rturn(int &rt){ int t=tr[rt].l; tr[rt].l=tr[t].r; tr[t].r=rt; tr[t].siz=tr[rt].siz; pushup(rt); rt=t;}void insert(int &rt, LL v){ if(!rt) { rt=++size; tr[rt].siz=1; tr[rt].v=v,tr[rt].sum=v; tr[rt].rnd=rand(); return; } tr[rt].siz++; if(v<=tr[rt].v) { insert(tr[rt].l,v); if(tr[tr[rt].l].rnd<tr[rt].rnd)rturn(rt); }else { insert(tr[rt].r,v); if(tr[tr[rt].r].rnd<tr[rt].rnd)lturn(rt); } pushup(rt);}void del(int &rt, LL v){ if(!rt)return; tr[rt].siz--; if(tr[rt].v==v) { if(tr[rt].l*tr[rt].r==0){rt=tr[rt].l+tr[rt].r;return;} if(tr[tr[rt].l].rnd<tr[tr[rt].r].rnd)rturn(rt),del(tr[rt].r,v); else lturn(rt),del(tr[rt].l,v); }else if(v<tr[rt].v)del(tr[rt].l,v); else del(tr[rt].r,v); pushup(rt);}LL query_val(int rt, int rnk){ if(tr[tr[rt].l].siz + 1 == rnk) return tr[rt].v; else if(rnk < tr[tr[rt].l].siz + 1) return query_val(tr[rt].l, rnk); else return query_val(tr[rt].r, rnk - tr[tr[rt].l].siz - 1);}LL query_PRe_sum(int rt, int rnk){ if(!rnk) return 0; if(tr[tr[rt].l].siz + 1 == rnk) return tr[tr[rt].l].sum + tr[rt].v; else if(rnk < tr[tr[rt].l].siz + 1) return query_pre_sum(tr[rt].l, rnk); else return tr[tr[rt].l].sum + tr[rt].v + query_pre_sum(tr[rt].r, rnk - tr[tr[rt].l].siz - 1);}LL query_sub_sum(int rt, int rnk){ if(!rnk) return 0; if(tr[tr[rt].l].siz + 1 == rnk) return tr[tr[rt].r].sum + tr[rt].v; else if(rnk < tr[tr[rt].l].siz + 1) return tr[tr[rt].r].sum + tr[rt].v + query_sub_sum(tr[rt].l, rnk); else return query_sub_sum(tr[rt].r, rnk - tr[tr[rt].l].siz - 1);}int main(){ scanf("%d%d", &n, &k); for(int i = 1; i <= n; i++) scanf("%lld", &h[i]); LL ans = 0x3f3f3f3f3f3f3f3fll; for(int i = 1; i <= n; i++){ if(i < k) insert(root, h[i]); else if(i == k){ insert(root, h[i]); LL mid = query_val(root, (k+1)>>1); LL sum1 = query_pre_sum(root, (k+1)>>1); LL sum2 = query_sub_sum(root, ((k+1)>>1) + 1); ans = min(ans, mid * ((k+1)>>1) - sum1 + sum2 - mid * (k - ((k+1)>>1))); } else{ del(root, h[i - k]); insert(root, h[i]); LL mid = query_val(root, (k+1)>>1); LL sum1 = query_pre_sum(root, (k+1)>>1); LL sum2 = query_sub_sum(root, ((k+1)>>1) + 1); ans = min(ans, mid * ((k+1)>>1) - sum1 + sum2 - mid * (k - ((k+1)>>1))); } } cout << ans << endl;}

上一篇：持久層框架--mybatis

下一篇：C# 哈希表