鏈接：https://ac.nowcoder.com/acm/contest/887/C
來源：牛客網(wǎng)

時(shí)間限制：C/C++ 3秒，其他語言6秒
空間限制：C/C++ 65536K，其他語言131072K
64bit IO Format: %lld
題目描述
The Wow village is often hit by wind and sand,the sandstorm seriously hindered the economic development of the Wow village.
There is a forest in front of the Wowo village, this forest can prevent the invasion of wind and sand. But there is a rule that the number of tallest trees in the forest should be more than half of all trees, so that it can prevent the invasion of wind and sand. Cutting down a tree need to cost a certain amount of money. Different kinds of trees cost different amounts of money. Wow village is also poor.
There are n kinds of trees. The number of i-th kind of trees is P_iP i , the height of i-th kind of trees is H_iHi , the cost of cutting down one i-th kind of trees is C_iC i .(Note: “cutting down a tree” means removing the tree from the forest, you can not cut the tree into another height.)

輸入描述:
The problem is multiple inputs (no more than 30 groups).
For each test case.
The first line contines one positive integers n (1 \leq n \leq 10^5)n(1≤n≤10 5 ),the kinds of trees.
Then followed n lines with each line three integers H_i (1 \leq H_i \leq 10^9)H i (1≤H i ≤10 9 )-the height of each tree, C_i (1 \leq C_i \leq 200)C i (1≤C i ≤200)-the cost of cutting down each tree, and P_i(1 \leq P_i\leq 10^9)P i(1≤P i≤10 9 )-the number of the tree.
輸出描述:
For each test case, you should output the minimum cost.
示例1
輸入
復(fù)制
2
5 1 1
1 10 1
2
5 1 2
3 2 3
輸出
復(fù)制
1
2

題意：n種樹，每種樹有一個(gè)高度，砍掉需要的價(jià)值，以及數(shù)量。
現(xiàn)在我們要把最高的樹的數(shù)目嚴(yán)格大于所有樹數(shù)目的一半。問所需要的最小價(jià)值是多少。
一開始以為是貪心，后來又想是dp。最后想的主席樹。。。
用主席樹還是權(quán)值線段樹都行，因?yàn)槲覀兦蟮氖?~i區(qū)間的。
（主席樹做法）我們先把高度由小到大排個(gè)序之后，建立各個(gè)版本的主席樹，我們就從高到低去遍歷所有種類的樹。假如當(dāng)前的樹的高度是H，那么所有大于H的樹都應(yīng)該被砍掉。除此之外，假如最高的樹的數(shù)目不嚴(yán)格大于一半，那么我們應(yīng)該去砍小于H的樹木，并且使這個(gè)值最小。這個(gè)就交給主席樹去做，我們?cè)谥飨瘶渲幸呀?jīng)統(tǒng)計(jì)出來了樹的數(shù)目，以及需要的花費(fèi)。就可以統(tǒng)計(jì)出砍k顆樹所需要的最小價(jià)值。
主席樹代碼如下：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define ll long long using namespace std;const int maxx=2e5+100; struct Node{ll h;ll v;ll num;bool operator <(const Node &a)const{return a.h>h;} }t[maxx]; struct node{ll l;ll r;ll sum;ll num; }p[maxx*40]; ll v[maxx]; ll root[maxx]; int n;ll numm;ll update(ll rot,ll l,ll r,ll pos,ll num) {ll cur=++numm;p[cur]=p[rot];p[cur].num+=(ll)num;p[cur].sum+=(ll)pos*(ll)num;if(l==r) return cur;ll mid=l+r>>1;if(pos<=mid) p[cur].l=update(p[rot].l,l,mid,pos,num);else p[cur].r=update(p[rot].r,mid+1,r,pos,num);return cur; } ll query(ll rot,ll l,ll r,ll num)//砍掉num棵樹 {if(l==r) return (ll)l*(ll)num;//如果到達(dá)了葉子節(jié)點(diǎn)，就砍掉num棵葉子節(jié)點(diǎn)。ll ans=p[p[rot].l].num;ll mid=l+r>>1;if(num<=ans) return query(p[rot].l,l,mid,num);//如果小于左子樹的樹數(shù)目else{return p[p[rot].l].sum+query(p[rot].r,mid+1,r,num-ans);//左子樹的數(shù)目不夠，就把左子樹的全都砍掉，剩下的去砍右子樹} }int main() {int tt;while(scanf("%d",&n)!=EOF){memset(v,0,sizeof(v));numm=0;for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&t[i].h,&t[i].v,&t[i].num);sort(t+1,t+1+n);for(int i=1;i<=n;i++) v[i]+=v[i-1]+t[i].num;for(int i=1;i<=n;i++){root[i]=update(root[i-1],1,210,t[i].v,t[i].num);//各個(gè)版本的主席樹}ll Max=1e18;ll tempnum=0;ll sum=0;ll money=0;for(int i=n;i>=1;i--){tempnum=0;while(t[i].h==t[i-1].h)//如果有高度相同的樹，就一起加上，因?yàn)樵}只說是高度一樣的樹，沒有說非得是種類相同的樹{tempnum+=t[i].v*t[i].num;sum+=t[i].num;i--;}sum+=t[i].num;tempnum+=t[i].v*t[i].num;ll temp=0;if(v[i-1]>=sum) temp=money+query(root[i-1],1,210,v[i-1]-sum+1);//至少要砍這些樹才能符合題意else temp=money;Max=min(Max,temp);money+=tempnum;sum=0;}printf("%lld\n",Max);} }

權(quán)值線段樹做法。
我承認(rèn)權(quán)值線段樹的做法做麻煩了。。因?yàn)槲沂前粗飨瘶涞乃枷胱鱿氯サ摹?br /> 我一開始把所有的信息都插入到了線段樹里。但是線段樹不像主席樹那樣有多個(gè)版本。所以統(tǒng)計(jì)完一棵樹之前就要把它刪掉。一開始沒有這樣做，wa成狗。0.00%的絕望。
代碼如下：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #define ll long long using namespace std;const int maxx=2e5+100; struct Node{ll h;ll v;ll num;bool operator<(const Node &a)const{return a.h>h;} }t[maxx]; struct node{ll l;ll r;ll sum;ll num; }p[maxx<<2]; ll v[maxx]; int n;void pushup(int cur) {p[cur].sum=p[cur<<1].sum+p[cur<<1|1].sum;p[cur].num=p[cur<<1].num+p[cur<<1|1].num; } void build(ll l,ll r,int cur) {p[cur].l=l;p[cur].r=r;p[cur].num=p[cur].sum=0;if(l==r) return ;ll mid=l+r>>1;build(l,mid,cur<<1);build(mid+1,r,cur<<1|1);pushup(cur); } void update(ll l,ll r,ll pos,ll num,int cur,int flag)//flag==0時(shí)代表著是刪除，flag==1時(shí)代表著添加。 {if(l==r){if(flag){p[cur].num+=num;p[cur].sum+=1LL*(l*num);}else{p[cur].num-=num;p[cur].sum-=1LL*num*l;}return ; }int mid=l+r>>1;if(pos<=mid) update(l,mid,pos,num,cur<<1,flag);else update(mid+1,r,pos,num,cur<<1|1,flag);pushup(cur); } ll query(ll l,ll r,int cur,ll num)//意思類似于主席樹的操作。 {if(num<=0) return 0;if(l==r) return (ll)num*(ll)l;ll mid=l+r>>1;ll ant=p[cur<<1].num;if(num<=ant) return query(l,mid,cur<<1,num);else return p[cur<<1].sum+query(mid+1,r,cur<<1|1,num-ant); } int main() {while(scanf("%d",&n)!=EOF){memset(v,0,sizeof(v));for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&t[i].h,&t[i].v,&t[i].num);sort(t+1,t+1+n);build(1,210,1);for(int i=1;i<=n;i++) {v[i]+=v[i-1]+t[i].num;update(1LL,210LL,t[i].v,t[i].num,1,1);//一開始把所有的節(jié)點(diǎn)信息都加進(jìn)去了，因?yàn)槲沂菑膎到1遍歷的。}ll Max=1e18;ll Money=0;ll sum=0;for(int i=n;i>=1;i--){ll cmoney=0;while(t[i].h==t[i-1].h){cmoney+=t[i].num*t[i].v;sum+=t[i].num;update(1LL,210LL,t[i].v,t[i].num,1,0);i--; }cmoney+=t[i].num*t[i].v;sum+=t[i].num;update(1LL,210LL,t[i].v,t[i].num,1,0);//在統(tǒng)計(jì)之前就要把它給刪除掉，因?yàn)椴粍h除有可能在刪比它高度小的樹的時(shí)候出現(xiàn)錯(cuò)誤。。因?yàn)楦叨缺人?#xff0c;價(jià)值不一定比它小。那么就算小了，就不對(duì)了。剩下的和主席樹大同小異，權(quán)值線段樹就是主席樹的前身嘛！！ll temp=0;if(v[i-1]>=sum) temp=Money+query(1,210,1,v[i-1]-sum+1);else temp=Money;Max=min(Max,temp); Money+=cmoney;sum=0;}printf("%lld\n",Max);}return 0; }

還是太菜了，要理解一會(huì)兒才能徹底明白。。
努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的Governing sand（权值线段树/主席树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。