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

题意

给出一个大小n的数组，和一个m，对应数组中每个数 i ，要在【0，i】的区间内删除若干个数（但是不能删除i），使得剩下的数的总和小于等于m，对于每一个i，求最少要删除多少个数；

思路

因为数组中的数的值最大就是100；所以我们可以遍历数组，遍历完将 a[i] 放cnt数组中；在遍历a数组中时我们只要在cnt数组中从大到小减数，减到小于m即可

代码

#include 
   
    #define maxn 200010using namespace std;int a[maxn], sum[maxn], cnt[200];int main(){   	int n, m;	cin >> n >> m;	for(int i = 1; i <= n; i++){   		cin >> a[i];		sum[i] = sum[i-1] + a[i];	}	for(int i = 1; i <= n; i++){   		if(sum[i] <= m){   			cout << 0 << " ";		}		else{   			int q = sum[i] - m;			int ans = 0;			for(int j = 100; j >= 0; j--){   				if(q <= 0){   					break;				}				int c = min(cnt[j], (q + (j - 1)) / j);				q -= c * j;				ans += c;			}			cout << ans << " ";		}		cnt[a[i]]++;	}	cout << endl;}