Description
N柱磚,希望有連續(xù)K柱的高度是一樣的. 你可以選擇以下兩個動作 1:從某柱磚的頂端拿一塊磚出來,丟掉不要了. 2:從倉庫中拿出一塊磚,放到另一柱.倉庫無限大. 現(xiàn)在希望用最小次數(shù)的動作完成任務(wù). Input
第一行給出N,K. (1 ≤ k ≤ n ≤ 100000), 下面N行,每行代表這柱磚的高度.0 ≤ hi ≤ 1000000 Output
最小的動作次數(shù) Sample Input 5 3
3
9
2
3
1 Sample Output 2
解題方法： 我們線性掃區(qū)間，然后每個區(qū)間的中位數(shù)肯定是這個區(qū)間的選取的高度。搞出這個高度后我們要將這個區(qū)間內(nèi)的所有的數(shù)與選取的高度作差取絕對值求和。所以轉(zhuǎn)化成，我們需要一種數(shù)據(jù)結(jié)構(gòu)支持刪點，加點，找排名為rnk的數(shù)，詢問部分求和。所以上個Treap就好了。至于求和，記個sum，比中位數(shù)小的用中位數(shù)乘個數(shù)減求和，比中位數(shù)大的用求和減中位數(shù)乘個數(shù)。其實就是平衡樹裸題了。 代碼如下：
#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;}新聞熱點
疑難解答
