2019牛客暑期多校训练营（第七场）-C Governing sand

爱被打了一巴掌 2021-10-30 02:36 235阅读 0赞

题目链接：https://ac.nowcoder.com/acm/contest/887/C

题意：有n种树，给出每种数的高度、移除的花费和数量，求最小花费是多少使得剩下树中最高的树的数量占一半以上。

思路：先按高度值进行排序，暴力枚举以哪种树为最高的树，对每次选择，要将高度值大于该树的其它树全砍掉，这个可以O(n)预处理得到。然后要砍掉高度值小于该树中的花费最小的一些树使得满足条件，注意到c<=200，那么可以保存每种花费的树的个数，从1到200枚举出需要移除的数量的最小花费即可。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cctype>
    using namespace std;
    
    const int maxn=1e5+5;
    typedef long long LL;
    int n;
    LL ans,num[maxn],C[205],pre,aft[maxn];
    struct node{
        LL h,c,p;
    }a[maxn];
    
    inline LL read(){
        LL x=0,f=0;char ch=0;
        while(!isdigit(ch)) {f|=ch=='-';ch=getchar();}
        while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
        return f?-x:x;
    }
    
    bool cmp(node x,node y){
        return x.h<y.h;
    }
    
    LL cal(LL x){
        LL res=0;
        for(int i=1;i<=200;++i){
            if(C[i]>=x){
                res+=i*x;
                break;
            }
            else{
                res+=i*C[i];
                x-=C[i];
            }
        }
        return res;
    }
    
    int main(){
        while(~scanf("%d",&n)){
            ans=0x3f3f3f3f3f3f3f3f;
            memset(C,0,sizeof(C));
            for(int i=1;i<=n;++i)
                a[i].h=read(),a[i].c=read(),a[i].p=read();
            sort(a+1,a+n+1,cmp);
            aft[n]=0;
            for(int i=n-1;i>=1;--i)
                aft[i]=aft[i+1]+a[i+1].c*a[i+1].p;
            int j;
            for(int i=1;i<=n;i=j){
                LL t1=a[i].p;
                num[i]=num[i-1]+a[i].p;
                for(j=i+1;j<=n&&a[j].h==a[i].h;++j){
                    num[j]=num[j-1]+a[j].p;
                    t1+=a[j].p;
                }
                LL tmp=num[j-1]-2*t1+1;
                if(tmp<=0)
                    pre=0;
                else
                    pre=cal(tmp);
                for(int k=i;k<j;++k)
                    C[a[k].c]+=a[k].p;
                ans=min(ans,pre+aft[j-1]);
            }
            printf("%lld\n",ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/FrankChen831X/p/11328610.html