P10087 [ROIR 2022 Day 1] 跳跃机器人 题解

· · 题解

写了半个小时，我是 fw 吗。

先假设从第一个点出发。机器人从第 i 个点跳到下一个点所需要的灵敏度是 d_i，而从第一个点出发到第 i 个点增加的灵活度是 i-1，所以如果机器人要成功跳出 i 点，它在初始的时候灵活度应该是 d_i-i+1。那么，答案应该是 \max\limits_{i=1}^{n}(d_i-i+1)。可以 O(n) 解决。

但是，题目要我们自己选择一个出发点。如果直接枚举每个出发点，程序是 O(n^2) 的，绝对过不了。

可以把从第 x 个点出发后的 n 个点拆成两个部分，第一个部分的点在 [x,n] 中，第二个部分的点在 [1,x-1] 中。把上面的答案迁移下来，那么从第 x 个点出发的答案应该是 \max(\max\limits_{i=x}^{n}(d_i-i+x),\max\limits_{i=1}^{x-1}(d_i-(i+n)+x))=\max(\max\limits_{i=x}^{n}(d_i-i+x),\max\limits_{i=1}^{x-1}(d_i-n-i+x))，程序的最终答案应该是 \min\limits_{x=1}^{n}(\max(\max\limits_{i=x}^{n}(d_i-i+x),\max\limits_{i=1}^{x-1}(d_i-n-i+x)))。

设 r_{i}=d_i-i,l_{i}=d_i-n-i，则答案为 \min\limits_{x=1}^{n}(\max(\max\limits_{i=1}^{x-1}(l_{i}+x),\max\limits_{i=x}^{n}(r_{i}+x)))=\min\limits_{x=1}^{n}(\max(\max\limits_{i=1}^{x-1}(l_{i}),\max\limits_{i=x}^{n}(r_{i}))+x)。可以发现，\max\limits_{i=1}^{x-1}(l_{i}),\max\limits_{i=x}^{n}(r_{i}) 中 l_i,r_i 的具体值不受 x 影响，x 只决定了取哪个区间的最大值。又可以发现，这两个区间分别是 [1,x-1] 和 [x,n]。所以实际上，可以先 O(n) 计算出 x 为 1 到 n 时 \max\limits_{i=1}^{x-1}(l_{i}),\max\limits_{i=x}^{n}(r_{i}) 分别的值（例如分别记为 L_{x-1},R_{x}），接下来计算的时候就可以直接用 \min\limits_{x=1}^{n}(\max(L_{x-1},R_{x})+x) 计算就变成 O(n) 的了。

写代码的时候注意数据范围和时空限制。首先，数组不能开 long long；其次，在 f=2 时注意乘法运算时先强转 long long；接着，区分哪里用 min，哪里用 max；然后，还要注意定的 -inf 要足够小（但不能太小）；最后，别输出反了。

#include<bits/stdc++.h>
using namespace std;
int d[11451919],l[11451919],r[11451919],L[11451919],R[11451919];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    int f;cin>>f;
    if(f==1){
        for(int i=1;i<=n;i++)cin>>d[i];
    }else{
        int m,x,y,z;cin>>m>>x>>y>>z;
        for(int i=1;i<=m;i++)cin>>d[i];
        for(int i=m+1;i<=n;i++)d[i]=(1ll*x*d[i-2]+1ll*y*d[i-1]+z)%1000000000+1;
    }
    for(int i=1;i<=n;i++){
        l[i]=d[i]-n-i;
        r[i]=d[i]-i;
    }
    L[0]=-0x7cff0102;
    for(int x=1;x<=n;x++){
        L[x]=max(L[x-1],l[x]);
    }
    R[n+1]=-0x7cff0102;
    for(int x=n;x>=1;x--){
        R[x]=max(R[x+1],r[x]);
    }
    int mn=0x7cff0102,pos=0xcff0102;
    for(int x=1;x<=n;x++){
        int t=max(L[x-1],R[x])+x;
        if(t<mn){
            pos=x;
            mn=t;
        }
    }
    cout<<mn<<" "<<pos;
    return 0;
}