【Codeforces 1185C2】Exam in BerSU (hard version)

要让前i个数字的和小于等于M.
问你最少要删掉前i-1个数字中的多少个数字,每个询问都是独立的。

【题解】

ti的范围很小。
所以N*MAX(TI)暴力枚举就行。
如果超过了M的话显然是优先把大的数字删掉。

【代码】

#include <iostream>

using namespace std;

const int INF = 100;

int n,M;

int rest[INF+10];

int main(){

    ios::sync_with_stdio(0),cin.tie(0);

    cin >> n >> M;

    for (int i = 1;i <= n;i++){

        int x;

        cin >> x;

        rest[x]++;

        int temp = 0;

        for (int j = 1;j <= 100;j++) temp = temp + rest[j]*j;

        int ans = 0;

        if (temp>M){

            for (int j = 100;temp>M && j >= 1;j--){

                int need = (temp-M-1)/j + 1;

                need = min(need,rest[j]);

                if (j==x){

                    need = min(need,rest[j]-1);

                }

                ans+=need;

                temp = temp - j*need;

            }

        }

        cout<<ans<<' ';

    }

    return 0;

}

巴特西

【Codeforces 1185C2】Exam in BerSU (hard version)

最新文章

热门文章