题目大意：给你一个序列，对于每个i，你可以选择1~i-1中任意多的数并将它删去，剩余的数（包括i）∑≤m，问对于每个i最少删几个数可以达到要求
题解：
考虑朴素的思想，对于每个i，我只需要删去最大的若干个使得∑≤m即可，时间复杂度O(n^2)
显然不可接受，考虑优化
显然可以看出，因为只需要删去最大的若干数，于是想到前K大，于是很自然想到用线段树
先离散化，只需要记录这个数是第几大，之后线段树维护区间和，每新加入一个点时加入这个点第几大的下标
询问时在线段树上二分出前K大即可，时间复杂度O(nlogn)
代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<cstring> #include<string> #define ll long long using namespace std; int TT,n; int ans[200001]; ll m; struct node { ll v; int bh,rk; }a[200001]; bool cmp(const node &T1,const node &T2){return T1.v<T2.v;} bool cmp2(const node &T1,const node &T2){return T1.bh<T2.bh;} ll sum[200001*5],cnt[200001*5]; int ask(int l,int r,ll v,int pos,ll tot) { if(sum[pos]+tot<=v)return cnt[pos]; else { int mid=l+r>>1; int t=ask(l,mid,v,pos<<1,tot); if(t==cnt[pos<<1])t+=ask(mid+1,r,v,pos<<1|1,tot+sum[pos<<1]); return t; } } void insert(int l,int r,ll v,int p,int pos) { if(l==r && l==p) { sum[pos]=v;cnt[pos]=1; return; } int mid=l+r>>1; if(p<=mid)insert(l,mid,v,p,pos<<1); else insert(mid+1,r,v,p,pos<<1|1); sum[pos]=sum[pos<<1]+sum[pos<<1|1]; cnt[pos]=cnt[pos<<1]+cnt[pos<<1|1]; } int main() { scanf("%d",&TT); while(TT--) { memset(sum,0,sizeof(sum)); memset(cnt,0,sizeof(cnt)); memset(ans,0,sizeof(ans)); scanf("%d%lld",&n,&m); for(int i=1;i<=n;i++){scanf("%lld",&a[i].v);a[i].bh=i;} sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++)a[i].rk=i; sort(a+1,a+1+n,cmp2); for(int i=1;i<=n;i++) { int t=ask(1,n,m-a[i].v,1,0); ans[i]=i-1-t; insert(1,n,a[i].v,a[i].rk,1); } for(int i=1;i<=n;i++)printf("%d ",ans[i]); printf("\n"); } return 0; }
心得：考场上很自然的想到，说明该部分知识掌握不错，继续加油
原文：https://www.cnblogs.com/worcher/p/11271148.html