虹色的北斗七星 题解

retep · 2022-07-25 01:00:39 · 题解

题目简述

你有一个长度为 n 的序列 a，它的一个区间 [l,r] 的价值为：

题目传送门：P8446 虹色的北斗七星

题目分析

这是道最优化问题，关键点在于对问题的转化。

题目中最显而易见的一点是 \max 与 \min 的位置一定是该区间的两个端点。

说实话这题本蒟蒻在比赛时想了很久，从动态规划到二分答案甚至连分治都考虑过，不过全部以不可行告终 要不是普及组不能超纲，我肯定浪费更多时间。

我发现自己在之前的思考中都潜意识地将 r-l+1 视作一个整体，也就是区间的长度，毕竟题目中也是用长度的意义来叙述的。

意识到这点后我开始想，是不是可以将 r-l+1 分开呢？1 很好说，只是个常量。关键在于 r-l，它俩其中一个是 \max 的下标，另一个则是 \min 的下标。

如果可以将 r 与 l 和 \max 与 \min 融合在一起就好了，因为那样的话就不用再受区间长度所困扰，只要求最大值和最小值就行了。可惜的是我们并不知道 \max 和 \min 哪个对应 r 哪个对应 l ......

于是乎，分类讨论！

1. 当 \max 对应的下标是 r，也就是 \max 在 \min 右边时：(\max-r)-(\min-l)-1

2. 当 \max 对应的下标是 l，也就是 \max 在 \min 左边时：(\max+l)-(\min+r)-1

解释一下，如果是第一种情况的话，我们建立 b 数组，使 b_i=a_i-i，然后计算区间价值时，直接计算:

可以看出这时算出来的值正好是区间的价值。第二种情况的话使 b_i=a_i+i 然后同理。

到这儿，我们已经可以将原问题转换为两个子问题了：

最后将两个子问题合并，既取其中的最大值，就得到了问题的最终答案。

code

#include<bits/stdc++.h>
#define N 4000005
#define ll long long
using namespace std;

int n,a[N],b[N],ans=-1;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int main(){
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read(),b[i]=a[i]-i;
    for(int i=1,mn=1e9;i<=n;i++){
        mn=min(b[i],mn);
        ans=max(ans,b[i]-mn);
        b[i]=a[i]+i;
    }
    for(int i=1,mx=-1e9;i<=n;i++){
        mx=max(b[i],mx);
        ans=max(ans,mx-b[i]);
    }
    cout<<ans-1;
    return 0;
}