本文共 1084 字，大约阅读时间需要 3 分钟。

【题解】

思路：有嗲眼熟的一道题。把问题转化成在前i-1个数中最多选出多少个数字和w[i]相加使得和小于等于m来考虑。

当需要进入一个数w[i]时，如果前面加起来的和+w[i]<=m，那么直接加进去就可以了；如果大于m了，那么就从最大的开始删，直到剩下的和+w[i]<=m，然后输出删掉的个数就可以了。

所以我一开始想的是两个优先队列维护，但是复杂度太高了因为有撤销删除的动作。我们可以用multiset维护选中的值，自动排序不去重。记得每次更新选择的最优元素集合即可，如果w[i]大于集合中最大的数就替换掉。

ps:告诉我原题是 CodeForces - 1185C2 Exam in BerSU (hard version) ，原来我做过怪不得眼熟。

【代码】

#include 
   
    using namespace std;const int maxn=2e5+10;#define ll long longll w[maxn];int cnt[maxn];multiset 
    
      mt;multiset 
     
       ::iterator it;int main(){    int T; scanf("%d",&T);    while(T--){         mt.clear();         int n; ll m;         scanf("%d %lld",&n,&m);         for(int i=1;i<=n;i++)            scanf("%lld",&w[i]);         cnt[1]=0;         ll sum=w[1];         mt.insert(w[1]);         for(int i=2;i<=n;i++){            it=mt.end();            it--;            ll last=*it;            ll now=sum;            if(sum+w[i]>m){                for(int j=mt.size()-1;it!=mt.end();it--,j--){                    sum-=*it;                    if(sum+w[i]<=m){                        cnt[i]=i-1-j;                        if(w[i]
     
    
   

转载地址：http://onben.baihongyu.com/