题解 | #盾与战锤#

盾与战锤

https://ac.nowcoder.com/acm/contest/11180/C

题目大意

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


解题思路

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

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

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

枚举攻击轮数的时间复杂度是调和级数,所以时间复杂度是 O(n log n)O(n\ log\ 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;
}

全部评论

相关推荐

三年之期已到我的offer快到碗里来:9硕都比不上9本
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务