[语言月赛202306] 信 题解

· · 题解

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;

视频题解