题解：P12709 [KOI 2021 Round 1] 采蜜

GreenMelon · 2025-07-15 16:06:15 · 题解

有三种情况：

• 一只蜜蜂在最左侧，另一只蜜蜂在中间，蜂巢在最右侧。则第一只蜜蜂能采到的蜂蜜总数就是从 a_2 到 a_n 的总和减去 a_i（i 为第二只蜜蜂起点所在位置），第二只蜜蜂能采到的蜂蜜总数为从 a_{i+1} 到 a_n 的总和。
• 一只蜜蜂在最右侧，另一只蜜蜂在中间，蜂巢在最左侧。与第一种情况同理，只是顺序不同；
• 一只蜜蜂在最左侧，另一只蜜蜂在最右侧，蜂巢在中间。则第一只蜜蜂能采到的蜂蜜总数为 a_2 到 a_i 的总和，第二只蜜蜂能采到的蜂蜜总数为 a_i 到 a_{n-1} 的总和

注意不要采集两只蜜蜂起点位置的蜂蜜。

答案就是两只蜜蜂能采到的蜂蜜总和的最大值。

由于 n 比较大，求区间和就使用前缀和优化。

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
#define mod 998244353
#define ll long long
int n, a[N], b[N], ans;
main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=b[i-1]+a[i];//前缀和数组
    }
    for(int i=2;i<n;i++) ans=max(ans, (b[n]-b[1]-a[i])+(b[n]-b[i]));
    for(int i=2;i<n;i++) ans=max(ans, (b[n-1]-a[i])+b[i-1]);
    for(int i=2;i<n;i++) ans=max(ans, (b[i]-b[1])+(b[n-1]-b[i-1]));
    cout<<ans;
}