原题链接: Find the answer

c++中,multiset是库中一个非常有用的类型,它可以看成一个序列,插入一个数,删除一个数都能够在O(logn)的时间内完成,而且他能时刻保证序列中的数是有序的,而且序列中可以存在重复的数。

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

具体操作请参考: multiset用法总结

解题思路:对于1007这道题,当放一个数x的时,先模拟判断,再插入序列中,进行合法判断,如果一个数不合法,则将它删去,为什么可以删去呢?因为一个数如果被判断不合法的话,那么接下来他也不会再被用了。

代码如下:

#include<set>
#include<iostream>
using namespace std;
typedef long long ll;
multiset<int> st;
ll sum;
void erase(ll x){
    st.erase(st.find(x));
    sum -= x;
}
void insert(ll x){
    st.insert(x);
    sum += x;
}
void solve(){
    sum = 0;
    st.clear();
    int n, m, tot = 0;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        int x, num = 0;
        scanf("%d", &x);
        auto it = st.end();
        ll tmp = sum;
        while(tmp + x > m){
            it--;
            tmp -= (*it);
            num++;
        }
        printf("%d ", tot + num);
        insert(x);
        while(sum > m){
            auto it = st.end();
            it--;
            erase((*it)); 
            tot++;
        }
    }
    printf("\n");
}
int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        solve();
    }
    return 0;
} 

参考:Hdu 6609 Find the answer

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄