题解

· · 题解

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

1.思路：

首先这道题要求：

所以本题暴力就好了。代码太长了，怎么办？直接 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;
}
  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];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;
}
  1. 方法三代码（使用前缀和并只存储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);
}