自动搬运

查看原文

来自洛谷，原作者为

	wangbinfeng 今天搞完大概就永远不会碰 OI 了，大家祝好！

搬运于2025-08-24 22:31:56，当前版本为作者最后更新于2021-06-25 12:30:45，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

大家好，我们又见面了。 （写题解实属不易，已经提交好几遍了，若有问题麻烦管理详细一点反馈，辛苦了）

1.思路：

首先这道题要求：

$8$ 片的披萨，每片上面有不同数量的蘑菇，找到连续的四片披萨，使得上面的蘑菇最多。

所以本题暴力就好了。代码太长了，怎么办？直接 sort 呗。然而这种缩短代码的方式有误，因为“找到连续的四片披萨”，所以只能多打一个双层循环了。

于是，我们快乐的打完了代码。

#include<bits/stdc++.h>
using namespace std;
int dat[8],ans,now;
int main(){
    for(int i=0;i<8;i++)cin>>dat[i];
    for(int i=0;i<8-3;i++){
        now=0;
        for(int j=i;j<i+4;j++)now+=dat[j];
        if(now>ans)ans=now;
    }
    cout<<ans;
}

第一个样例开开心心的 水 过了，但第二个始终过不了。用手模拟也是 $18$ ，为什么样例是 $19$ ？ 一定是样例错了。 我们仔细的再读一遍题，会发现： $S_1$ , $S_2$ , $S_3$ , $S_4$ 是一组合法的 $4$ 片披萨，但 $S_7$ , $S_8$ , $S_1$ , $S_2$ 也是合法的序列 （一些 $35$ 分的同学看这里了） 。

怎么弄呢？学过循环队列的同学应该都会，直接在每次取数据时 对元素数量（ $8$ ）取余。没搞懂有一种简单的方法：直接把内容存储两遍就好了。没搞懂的同学怎么办？ 自己去学循环队列。 有一种简单的方法：直接把内容存储两遍就好了。

如果你觉得这 $2$ 种方式太简单了，那就在来第 $3$ 中解法吧（方法借鉴 @SHM ）!

由连续的披萨，结合 线段树、树状数组 前缀和可以轻松想到使用前缀和来实现记录，但是只要求4个元素的和，而并不需要要求的最后一个元素之前所有元素之和，怎么办呢？设四个元素开始为 $x$ ，最后一个元素为 $y$ ，则 $x$ 到 $y$ 的和就等于 $y$ 的前缀和减 $x$ 的前缀和。

又遇到了老问题：披萨是一个环。解决方法也很简单有2种解法。其实这两种解法与上文中的方法相似，只是第二种需要一些很小的变动，所以我们分析一下第2种解法。

先分析如何取出在环两端的交接：左侧选 $i$ 个，右侧选 $4-i$ 个即为结果。

如图：

2.代码

1. 方法一代码（取余）：

#include<bits/stdc++.h>
using namespace std;
int dat[20],ans,now;
int main(){
    for(int i=0;i<8;i++){cin>>dat[i];}
    for(int i=0;i<8;i++){
        now=0;
        for(int j=i,k=0;k<4;j=(j+1)%8,k++)now+=dat[j];
        if(now>ans)ans=now;
    }
    cout<<ans;
}

2. 方法二代码（存储两遍）：

#include<bits/stdc++.h>
using namespace std;
int dat[20],ans,now;
int main(){
    for(int i=0;i<8;i++){cin>>dat[i];dat[i+8]=dat[i];}
    for(int i=0;i<16;i++){
        now=0;
        for(int j=i;j<i+4;j++)now+=dat[j];
        if(now>ans)ans=now;
    }
    cout<<ans;
}

3. 方法三代码（使用前缀和并只存储1遍）：

//by @_SHM_,thoughts and code if infringement please inform in the comment area, I will delete.
#include <cstdio>
int x[9], a;
int maxn = 0;
int main() {
    for (int i = 1; i <= 8; i++) {
        scanf ("%d", &a);
        x[i] = a + x[i - 1];
    }
    for (int i = 4; i <= 8; i++) {
        if ((x[i] - x[i - 4]) > maxn) maxn = (x[i] - x[i - 4]);
        //前缀和
        //printf ("%d %d %d\n", x[i], (x[i] - x[i - 4]), maxn);
    }
    for (int i = 1; i <= 3; i++) {
        if (((x[8] - x[8 - (4 - i)]) + x[i]) > maxn) maxn = ((x[8] - x[8 - (4 - i)]) + x[i]);
        //左侧选i个，右侧选(4-i)个，因为总和只有4个
    }
    printf ("%d\n", maxn);
}