Governing sand

题意

森林里有m种树木，每种树木有一定高度，并且砍掉他要消耗一定的代价，问消耗最少多少代价可以使得森林中最高的树木大于所有树的一半

分析

复杂度分析:n 1e5种树木，并且砍树肯定是从便宜的砍，有区间性，可以考虑线段树，每次枚举一种高度，先把高于其高度的全部砍掉，再砍低于他的使得满足大于一半的条件，砍低于他的肯定是从花费低的开始砍，所以就是一个选前k小的问题，这样就是一颗权值线段树的事情了

坑点：不同种的树木可能高度相同

#include<bits/stdc++.h>

#define pb push_back

#define F first

#define S second

#define pii pair<int,int>

#define mkp make_pair

typedef long long ll;

#define int long long

using namespace std;

const int maxn =1e5+5;

ll tr[maxn<<2];

int sz,n;

int c[maxn],id[maxn];

ll sum[maxn];

struct Node{

    int h,p,c;

}a[maxn];

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

    sum[o]=tr[o]=0;

    if(l==r)return ;

    int mid=l+r>>1;

    build(o<<1,l,mid);

    build(o<<1|1,mid+1,r);

}

void update(int o,int l,int r,int p,int v){

    if(l==r){

        tr[o]+=v;

        sum[o]+=v*c[p];

    }

    else {

        int mid=l+r>>1;

        if(p<=mid)update(o<<1,l,mid,p,v);

        else update(o<<1|1,mid+1,r,p,v);

        tr[o]=tr[o<<1|1]+tr[o<<1];

        sum[o]=sum[o<<1]+sum[o<<1|1];

    }

}

ll query(int o,int l,int r,int num){

    if(l==r){

        return min(1ll*num,tr[o])*1ll*c[l];

    }

    int mid=l+r>>1;

    if(tr[o<<1]>=num)return query(o<<1,l,mid,num);

    else return sum[o<<1]+query(o<<1|1,mid+1,r,num-tr[o<<1]);

}

int32_t main(){

        while(scanf("%lld",&n)!=EOF){

        long long sumcost=0;

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

            scanf("%lld%lld%lld",&a[i].h,&a[i].c,&a[i].p);

            sumcost+=a[i].p*a[i].c;

            c[i]=a[i].c;

        }

        sort(c+1,c+1+n);

        sz=unique(c+1,c+1+n)-(c+1);

        build(1,1,sz);

        sort(a+1,a+1+n,[](Node a,Node b){

                return a.h<b.h;});

        long long qnum=0;

        long long ans=1e18;

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

            id[i]=lower_bound(c+1,c+1+sz,a[i].c)-c;

        }

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

            int p=i+1;

            ll nowhnum=a[i].p;

            int cnt=0;

            while(p<=n&&a[p].h==a[i].h){

                nowhnum+=a[p].p;

                cnt++;

                p++;

            }

                for(int j=i;j<=cnt+i;j++){

                    sumcost-=a[j].p*a[j].c;

                }

                if(nowhnum>qnum){

                    ans=min(sumcost,ans);

                }

                else {

                    ans=min(ans,sumcost+query(1,1,sz,qnum-nowhnum+1));

                }

                for(int j=i;j<=cnt+i;j++){

                    qnum+=a[j].p;

                    update(1,1,sz,id[j],a[j].p);

                }

                i=p;

        }

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

    }

    return 0;

}

巴特西

2019牛客训练赛第七场 C Governing sand 权值线段树+贪心

Governing sand

题意

分析

最新文章

热门文章