牛客多校第七场 C Governing sand 线段树

题意：

有一个树林，树林中不同种类的树有不同的数量，高度，砍伐它们的价格。现在要求砍掉一些树，使得高度最高的树占剩下的树的总数的一半以上，求最小花费。

题解：

用线段树维护不同种类树的信息，叶子节点从左到右存储单棵砍伐花费最小的树，从高度由高到低枚举树的种类，每次记这种树为留下的最高的树，每次将此种树从线段树上删除，然后求线段树上，使得矮树与高树比例满足要求的前缀和，还要记录比它高的树砍掉的总花费。

注意多种树同一高度要特殊处理。

#include<bits/stdc++.h>

#define MAXN 100005

#define LL long long

using namespace std;

struct Node{

    int l,r;

    int oneval;

    LL sumnum;

    LL sumval;

}node[MAXN<<];

struct Tree{

    int oneval;

    int num;

    int height;

    int valrank;

}tree[MAXN];

inline bool cmp1(const Tree &a,const Tree &b){

    return a.oneval<b.oneval;

}

inline bool cmp2(const Tree &a,const Tree &b){

    return a.height>b.height;

}

void build(int l,int r,int x){

    node[x].l=l;

    node[x].r=r;

    if(l==r){

        node[x].sumnum=tree[l].num;

        node[x].oneval=tree[l].oneval;

        node[x].sumval=1LL*tree[l].num*tree[l].oneval;

        return ;

    }else{

        int mid=(l+r)/;

        build(l,mid,x*);

        build(mid+,r,x*+);

    }

    node[x].sumnum=node[*x].sumnum+node[*x+].sumnum;

    node[x].sumval=node[*x].sumval+node[*x+].sumval;

    return ;

}

//LL query(int l,int r,int x){

//    if(l<=node[x].l && node[x].r<=r)return node[x].exis;

//    if(node[x].r<l || r<node[x].l)return 0;

//    LL ans=0;

//    if(l<=node[x*2].r)ans+=query(l,r,2*x);

//    if(node[x*2+1].l<=r)ans+=query(l,r,2*x+1);

//    return ans;

//}

void erase(int id,int x){

    if(node[x].l==node[x].r){

        node[x].sumnum=;

        node[x].sumval=;

        node[x].oneval=;

        return ;

    }

    if(id<=node[x*].r){

        erase(id,x*);

    }else{

        erase(id,x*+);

    }

    node[x].sumval=node[x*].sumval+node[x*+].sumval;

    node[x].sumnum=node[x*].sumnum+node[x*+].sumnum;

    return ;

}

LL bsearch(LL last,int x){

    if(last<=)return ;

    if(node[x].l==node[x].r)return last*node[x].oneval;

    if(node[x].sumnum==last)return node[x].sumval;

    if(node[x].sumnum>last){

        if(last<=node[x*].sumnum)return bsearch(last,x*);

        else return node[x*].sumval+bsearch(last-node[x*].sumnum,x*+);

    }

}

int main(){

    int n;

    while(~scanf("%d",&n)){

        LL nowtrees=;

        LL nowcost=;

        LL minn=0x3f3f3f3f3f3f3f3f;

        for(int i=;i<=n;i++){

            scanf("%d %d %d",&tree[i].height,&tree[i].oneval,&tree[i].num);

            nowtrees+=tree[i].num;

        }

        sort(tree+,tree++n,cmp1);

        for(int i=;i<=n;i++){

            tree[i].valrank=i;

        }

        build(,n,);

        sort(tree+,tree++n,cmp2);

        for(int i=;i<=n;i++){

            LL nextcost=;

            LL talltrees=;

            while(i<n && tree[i+].height==tree[i].height){

                nowtrees-=tree[i].num;

                talltrees+=tree[i].num;

                erase(tree[i].valrank,);

                nextcost+=1LL*tree[i].num*tree[i].oneval;

                ++i;

            }

            nowtrees-=tree[i].num;

            talltrees+=tree[i].num;

            erase(tree[i].valrank,);

            nextcost+=1LL*tree[i].num*tree[i].oneval;

            minn=min(minn,nowcost+bsearch(nowtrees-talltrees+,));

//          printf("time%d:%lld\n",i,nowcost+bsearch(nowtrees-talltrees+1,1));

            nowcost+=nextcost;

        }

        printf("%lld\n",minn);

    }

}

巴特西

牛客多校第七场 C Governing sand 线段树

最新文章

热门文章