【树状数组】【2019hdu多校】Find the answer

客官°小女子只卖身不卖艺 2023-06-01 08:46 17阅读 0赞

题意：每次从1到i-1中选择最少的数减为0，确保1到i的前缀和小于m，我们离散化，从小到大排序，按照输入顺序每遍历一个就插入到树状数组在排序过后的位置，二分位置确保树状数组的前缀和刚好小于/等于m-a\[i\]（当前i必选），因为从小到大排序确保了现有的小的尽量多选，大的都删掉。

#include<bits/stdc++.h>
    #define ll long long 
    #define ull unsigned long long
    using namespace std;
    const int N = 200000 + 5;
    int q,n;
    ll m;
    struct node
    {
        int num;
        ll sum;
    }c[200005];
    struct nod
    {
        int id;
        ll w;
    }a[200005];
    int mp[200005];
    bool cmp(nod a,nod b)
    {
        if(a.w==b.w)
            return a.id<b.id;
        return a.w<b.w;
    }
    void add(int x,ll y)
    {
        for(;x<=n;x+=x&-x)
        {
            c[x].sum+=y;
            c[x].num++;
        }
    }
    ll ask_sum(int x)
    {
        ll ret=0;
        for(;x;x-=x&-x)
        {
            ret+=c[x].sum;
            //cout<<x<<endl;
        }
        return ret;
    }
    ll ask_num(int x)
    {
        ll ret=0;
        for(;x;x-=x&-x)
        {
            ret+=c[x].num;
        }
        return ret;
    }
    int half_find(ll x)
    {
        int l=0,r=n;
        int mid=(l+r)>>1;
        while(l<=r)
        {
            //cout<<mid<<endl;
            mid=(l+r)>>1;
            if(ask_sum(mid)>x)
            {
                r=mid-1;
            }
            else
            {
                l=mid+1;
            }
            //cout<<l<<" "<<r<<" "<<mid<<endl;
        }
        //cout<<r<<endl;
        return ask_num(r);
    }
    int main()
    {
        int x=3;
        //for(;x;x-=x&-x)
            //cout<<x<<endl;
        scanf("%d",&q);
        //cout<<ask_num(7)<<endl;
        while(q--)
        {
            scanf("%d %lld",&n,&m);
            for(int i=1;i<=n;i++)
            {
                scanf("%lld",&a[i].w);
                a[i].id=i;
                c[i].num=c[i].sum=0;
            }
            sort(a+1,a+n+1,cmp);
            for(int i=1;i<=n;i++)
            {
                //cout<<a[i].id<<endl;
                mp[a[i].id]=i;
            }
            printf("0");
            add(mp[1],a[mp[1]].w);
            for(int i=2;i<=n;i++)
            {
                printf(" %lld",i-1-half_find(m-a[mp[i]].w));
                add(mp[i],a[mp[i]].w);
            }
            printf("\n");
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Diliiiii/p/11266167.html