2019 杭电 多校第3场 1007 Find the answer （HDU 6609）

红黑树赛高，封装STL赛高！

有时候选择比努力更重要，这一题的参考做法是线段树，然而比赛时我一直想要用优先队列做，遗憾的是优先队列无法访问非顶端元素，写出来之后会无限TLE。。。用multiset就完美实现了比赛时的思路，遗憾的是之前对multiset不够熟悉，可惜。
multiset内部采用红黑树实现。
multiset相关信息：http://www.cplusplus.com/reference/set/multiset/

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
multiset<int> ss;
const int maxn = 200010;
int a[maxn];
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        ss.clear();
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
        }
        ll sum=a[0];
        int tmp=0;
        multiset<int>::iterator j;
        printf("0 ");
        ss.insert(a[0]);
        for(int i=1 ;i<n ;i++)
        {
            int ans=0;
            ll sum0=sum;
            j=ss.end();
            while(sum0+a[i]>m)
            {
                j--;
                sum0-=*j;
                ans++;
            }
            printf("%d ",ans+tmp);
            ss.insert(a[i]);
            sum+=a[i];
            j=ss.end();
            while(sum>m)
            {
                j--;
                sum-=*j;
                tmp++;
                ss.erase(ss.find(*j));
            }
        }
        puts("");
    }
    return 0;
}