求助第四题,孩子真的想不通

为什么拖到最后不可以,等到不行了可以一次回满啊,和前面掉一点回一点有什么区别吗

感谢感谢

void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		b[i] = b[i - 1] + a[i]; // 前缀和
		if (a[i] == 0)
			v[++cnt] = i; // 统计回血的地方
	}
	if (m > b[n]) {
		cout << n - 1;
	} else {
		k = m;
		for (int i = 2 ; i <= cnt && m > 0; i++) {
			if (b[v[i]] - b[v[i - 1]] >= m) { // 下一阶段要扣的血
				res += k - m;
				m = k;
			}
			m -= (b[v[i]] - b[v[i - 1]]);
		}
		if (m > 0)
			cout << res + n - 1;
		else cout << "NO" ;
	}
}

全部评论
例:m=8 a: 1 0 1 0 5 0 2 0 如果拖到最后的话是在第三个0处回复,消耗1+1+5=7的时间 而不拖到最后的话只需要在第一个和第二个0处回复,共消耗1+1=2的时间 总之,恢复消耗的时间多少看的是你最后一次恢复前被扣的总生命,所以最后一次恢复应该越早越好,也就是找到最靠前且满足后缀和<m的0的位置,对应第二种思想;而你把恢复拖到最后的话意味着你最后一次回复的位置可能比较靠后,那在这之前你被扣的生命可能就更多,恢复消耗的时间就更多
3
送花
回复
分享
发布于 01-05 23:34 江苏

相关推荐

点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务