HDU多校联赛2019Round3. 1007（HDU6609） Find the answer 题解

╰半夏微凉° 2023-08-17 15:35 95阅读 0赞

原题链接:[Find the answer][]  
题目大意：给你\\(n\\)个数，每一个数不超过\\(m\\)，对于每一个数\\(a\_i\\)，你要从\\(a\_1,a\_2,...,a\_\{i-1\}\\)中删掉一些数，使得 \\\[ \{ \{\\sum\_\{j=1\}^i \{a\_j\}\} \\leq m\} \\\]，求对于每一个\\(i \\in \[1,n\]\\)，求要删掉的数的最小数量。  
题解：我们先考虑只有一次询问的情况，肯定是贪心，将最大的删去，一次的复杂度为\\(O(n)\\)，\\(n\\)次的复杂度便为\\(O(n^2)\\)，但是，这是每一次重新算，我们发现，在大部分情况下，第\\(i\\)个删除的数与第\\(i+1\\)个删除的数有很大部分是一样的，改变就是新增的\\(a\_i\\)，所以我们就可以考虑莫队算法，至于维护序列有序，可以用set来完成，复杂度不大靠谱，但是能过。  
代码：

#include <set>
    #include <cstdio>
    using namespace std;
    #define Maxn 200000
    #define ll long long
    int w[Maxn+5];
    int n,m;
    multiset<int> st;
    int main(){
        int t;
        scanf("%d",&t);
        ll sum;
        multiset<int>::iterator it_1;
        int ans;
        while(t--){
            st.clear();
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++){
                scanf("%d",&w[i]);
            }
            sum=0;
            printf("0 ");
            st.insert(w[1]);
            sum+=w[1];
            it_1=st.end();
            ans=0;
            for(int i=2;i<=n;i++){
                sum+=w[i];
                while(sum>m){
                    it_1--;
                    ans++;
                    sum-=(*it_1);
                }
                printf("%d ",ans);
                st.insert(w[i]);
                if(it_1!=st.end()&&w[i]>=(*it_1)){
                    sum-=w[i];
                    ans++;
                    while(sum+(*it_1)<=m){
                        sum+=(*it_1);
                        ans--;
                        it_1++;
                    }
                }
            }
            puts("");
        }
        return 0;
    }

转载于:https://www.cnblogs.com/withhope/p/11268580.html

[Find the answer]: http://acm.hdu.edu.cn/showproblem.php?pid=6609