题目大意

给出一个攻击序列和s，对于一个k，敌人每k秒可以恢复一个大小为s的护盾，而你要找攻击序列的一个子序列来攻击敌人（每个数表示造成的伤害），对于所有$k\in [1,n]k\backslash in[1,n]$，求出最多造成伤害

解题思路

题目可以看作每一轮有一个大小为s的盾，且可以攻击k次

可以先对攻击序列进行排序，枚举攻击多少轮，然后贪心求攻击伤害

当无法破盾时，s会大于攻击伤害，那么会造成负贡献，而在枚举更小的轮数时，这个负贡献会被舍去，所以这种枚举的方法是正确的

枚举攻击轮数的时间复杂度是调和级数，所以时间复杂度是 $O(nlogn)O(n\backslash \; log\backslash \; n)$

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 2000210
using namespace std;
ll n,s,ans,a[N],sum[N];
int main()
{
	scanf("%lld%lld",&n,&s);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
		a[i]=-a[i];
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n*2;++i)
		sum[i]=-a[i]+sum[i-1];
	for(int i=1;i<=n;++i){
		ans=0;
		for(int j=i;j<n+i;j+=i)//可能最后一轮没有选完，但有正贡献
			ans=max(ans,sum[j]-s*(j/i));
		printf("%lld\n",ans);
	}
	return 0;
}