这题写的我好难受，因为暴力优化到极致还是过不了。

:::info[暴力代码]

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll N=4e5+10;
int n,ans;
int a[N];
struct ios{
    inline char gc(){
        static const int IN_LEN=1<<18|1;
        static char buf[IN_LEN],*s,*t;
        return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
    }
    template <typename _Tp> inline ios & operator >> (_Tp&x){
        static char ch,sgn; ch = gc(), sgn = 0;
        for(;!isdigit(ch);ch=gc()){if(ch==-1)return *this;sgn|=ch=='-';}
        for(x=0;isdigit(ch);ch=gc())x=x*10+(ch^'0');
        sgn&&(x=-x); return *this;
    }
}io;
#define cin io
int main(){
    cin>>n;
    n=n*2+2;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=1;i<n;i+=2){
        for(int j=i+1;j<=n;j+=2){
            if(a[i]+a[j]<=ans) continue;
            ans=a[i]+a[j];
        }
    }
    printf("%d",ans);
    return 0;
}

:::

思路（正解）

当我们安排 VIP 用户的座位时，不难发现，两者不能同时在奇数或者同时在偶数位置。如果这样安排，剩余位置区块的座位数就会变成奇数，团体不能坐。

接下来就是求出两个 VIP 的位置。

暴力枚举的时间复杂度：$\mathcal{O(n^2)}=\mathcal{O(4\times {10}^{10})}$，会 TLE。

优化暴力（剪枝）：

• 最快：$\mathcal{O(n)}$。

• 最慢：$\mathcal{O(n^2)}$。

显然会超时。

不妨预处理后缀最大值。

• 设 $b_i=\begin{cases}\max(b_{i+1},a_i), & i\bmod 2=1, \\ b_{i+1}, & i\bmod 2=0. \end{cases}$。

• 循环：for(int i=1;i<n;i+=2)，$ans=\max(ans,a_i+b_{i+1})$。

最后输出 $ans$，就是答案。

没有很懂？解释一下：

• 如果 $i$ 为偶数，说明这个位置需要求后缀最大值，更新 $b_i$。否则，保留上一个偶数位置的值。

• $ans$ 是区间 $[1,i]$ 中，可选位置的最大值。

• $a_i+b_{i+1}$ 表示当前位置的舒适度与区间 $[i+1,n]$ 的舒适度最大值的和。

实现

既然是后缀最大值，那么肯定要从 $n$ 循环到 $1$（这个都知道吧)。

(a&1)==a%2，按位与快一些。

按照刚刚的 $b_i$ 赋值逻辑，不难写出代码：

for(int i=n;i>=1;--i){
    b[i]=b[i+1];
    if(!(i&1)) b[i]=max(b[i+1],a[i]);
}

易错点

1. 按位运算和其他运算一起用的时候不打括号。

2. 循环没有遍历到 $2n+2$。

3. 求答案最大值的时候，$b_i$ 的 $i$ 没有加 $1$（不然取的值是上一个偶数的）。

Code

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll N=4e5+10;
int n,ans;
int a[N],b[N];
int main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n;
    n=n*2+2;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=n;i>=1;--i){
        b[i]=b[i+1];
        if(!(i&1)) b[i]=max(b[i+1],a[i]);
    }
    for(int i=1;i<n;i+=2){
        ans=max(ans,a[i]+b[i+1]);
    }
    cout<<ans;
    return 0;
}

附

上图 By doubao。