Exam in BerSU (hard version) 这道题是属于codeforce上的一道题，说明不会用到一些特别难写的数据结构，这道题是要你维护一个关于整数的多重集合，然后给你一个背包容量，查询用这个背包最多可以装多少个该集合里的数，显然，每次取走集合中最小的那个数，我们的背包才能装的更多。所以该集合要维护成有序集。 我们对该有序集要实行两个功能:1.插入新元素。2.查询前n小的数之和。 这道题用splay的话复杂度是插入+查询前n小的数=logn，但是splay太难写了，想了想，用树状数组加二分就可以实现这个功能，复杂度logn^2，但是代码要简洁的多！
#include<cstring> #include<stdio.h> #include<cmath> #include<map> #include<vector> #include<set> #include<sstream> #include<queue> #include<algorithm> #include<stack> #include<cstdlib> #include<deque> #include<bitset> #include<iostream> #define FIN freopen("D://debug//in.txt","r",stdin); #define FOUT freopen("D://debug//out.txt","w",stdout); #define FDATA freopen("D://debug//data.txt","w",stdout); using namespace std; typedef long long int ll; const int maxn=2e5+5; int n,m; int a[maxn],b[maxn]; int a2[maxn];ll b2[maxn]; void add1(int d,int v){ while(d<=m){ a2[d]+=v;d+=d&-d; } } void add2(int d,int v){ while(d<=m){ b2[d]+=v;d+=d&-d; } } int sum1(int d){ int ans=0; while(d){ ans+=a2[d];d-=d&-d; } return ans; } ll sum2(int d){ ll ans=0; while(d){ ans+=b2[d];d-=d&-d; } return ans; } int h(int M){ int low=1,hign=m; while(low<=hign){ int mid=(low+hign)/2; if(sum2(mid)>=M)hign=mid-1; else low=mid+1; } int k=b[low-1],cnt=sum1(low); ll ans=sum2(low); return (ans-M)%k==0?cnt-(ans-M)/k:cnt-(ans-M)/k-1; } int f(int x){ return (lower_bound(b,b+m,x)-b)+1; } int main(){ //FIN int v; cin>>n>>v;m=0; for(int i=1;i<=n;i++)cin>>a[i],b[m++]=a[i]; sort(b,b+m); m=unique(b,b+m)-b; ll sum=0; for(int i=1;i<=n;i++){ sum+=a[i]; if(sum<=v){ printf("0%c",i==n?'\n':' '); } else printf("%d%c",i-1-h(v-a[i]),i==n?'\n':' '); int pos=f(a[i]); add1(pos,1); add2(pos,a[i]); } }我想的测试数据: 7 100 1 1 1 99 1 99 96
