自动搬运

查看原文

来自洛谷，原作者为

	未来姚班zyl 欢迎加入粉丝团！https://www.luogu.com.cn/team/72518|AFO

搬运于2025-08-24 21:15:00，当前版本为作者最后更新于2023-06-08 20:01:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Source & Knowledge

2023 年 6 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

zyl 按顺序拆开若干封信，信由信纸，信封和礼物三部分组成，给定了信纸与信封的单位质量，信纸与信封的面积，按照给定规则求出惊喜值，并给出过程中的最大值和最终的惊喜值。

题目分析

本题考察题目理解和代码实现能力。

本题题面还是不短的，需要认真读题以免丢失细节。我们来依次处理需要的信息。

首先判断有无礼物。显然，对于每一封信，礼物的重量等于总重量减去信封信纸的总重量。对于信封信纸，它们各自的重量等于单位面积的重量乘上它们的面积。故礼物的重量 $M'=M-xS-ys$。如果 $M'>0$ 则说明有礼物，否则没有礼物。

接下来要处理连续有/无礼物的信封的数量。这里我们可以开两个变量 $cnta$ 和 $cntb$，分别表示连续有礼物的信封的数量和连续没有礼物的信封的数量。当现在处理的信封中有礼物时，将 $cntb$ 置零，$cnta$ 增加一；反之，将 $cnta$ 置零，$cntb$ 增加一。这样就能时刻维护连续有/无礼物的信封的数量了。

接下来就是计算惊喜值了。如果没有礼物时，按照题意，只需判断 $cntb$ 是否达到了 $b$。如果达到了，惊喜就得折半（即除以二），向下取整。由于 c++ 中正数的运算本就是向下取整，所以可以放心除。如果有礼物，按照题意，首先将惊喜值加上 $M'$。然后，判断 $M'$ 与信封信纸的总质量 $xS+ys$ 的大小关系。如果 $M'$ 更大，则惊喜值需加上 $0.5M'$，向上取整。这里向上取整可以写成 $(M'+1) / 2$。如果 $cnta$ 达到了 $a$，则惊喜值翻倍（即乘以二）。然后用一个变量记录过程中的最大值就可以了。

注意惊喜值可能会达到 $10^{18}$，所以要用 long long 类型存储。

核心代码如下：

for(int i=1;i<=n;i++){
	scanf("%d%d%d",&S,&s,&M);
	int m = M - S * x + s * y;
	if(m){
		cnta++,cntb = 0;
		now += m;
		if(m > S * x - s * y)now += (m + 1) / 2;
		if(cnta >= a)now *= 2;
		ans = max(ans,now);
	}
	else {
		cntb++,cnta = 0;
		if(cntb >= b)now /= 2;
	}
}
cout <<ans<<" "<<now;

视频题解