写了半个小时，我是 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;
}

样例说明：

在第二个示例中，距离数组为 $[1, 2, 3, 4, 5, 18, 45, 112, 273, 662]$。

根据公式计算 $d_6$ 到 $d_{10}$ 的值：

• $d_6 = ((1 \cdot d_4 + 2 \cdot d_5 + 3) \bmod 10^9) + 1 = ((1 \cdot 4 + 2 \cdot 5 + 3) \bmod 10^9) + 1 = 18$；
• $d_7 = ((1 \cdot d_5 + 2 \cdot d_6 + 3) \bmod 10^9) + 1 = ((1 \cdot 5 + 2 \cdot 18 + 3) \bmod 10^9) + 1 = 45$；
• $d_8 = ((1 \cdot d_6 + 2 \cdot d_7 + 3) \bmod 10^9) + 1 = ((1 \cdot 18 + 2 \cdot 45 + 3) \bmod 10^9) + 1 = 112$；
• $d_9 = ((1 \cdot d_7 + 2 \cdot d_8 + 3) \bmod 10^9) + 1 = ((1 \cdot 45 + 2 \cdot 112 + 3) \bmod 10^9) + 1 = 273$；
• $d_{10} = ((1 \cdot d_8 + 2 \cdot d_9 + 3) \bmod 10^9) + 1 = ((1 \cdot 112 + 2 \cdot 273 + 3) \bmod 10^9) + 1 = 662$。

数据范围：

对于 $100\%$ 的数据，$3 \le n \le 10^7$。当 $f=1$ 时 $1 \le d_i \le 10^9$，当 $f=2$ 时 $2 \le m \le \min(n, 10^5)$，$0 \le x, y, z \le 10^9$，$1 \le c_i \le 10^9$。

动态规划优化：

#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;
}

单调队列 + 空间压缩（不压也能过）：

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct nint{
	int a;
	int t;
};
deque<nint>mx;
void pmx(nint x){
	while(!mx.empty()&&mx.front().a<=x.a)mx.pop_front();
	mx.push_front(x);
}
int d[114514];
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n,f;cin>>n>>f;
	int m,x,y,z;
	if(f==1){
		for(int i=1;i<=n;i++){
			int k;cin>>k;d[i]=k;
			nint temp{k-i,i};
			pmx(temp);
		}
	}else{
		cin>>m>>x>>y>>z;
		int i_2=0,i_1=0;
		for(int i=1;i<=m;i++){
			int k;cin>>k;d[i]=k;
			nint temp{k-i,i};
			pmx(temp);
			i_2=i_1;i_1=k;
		}
		for(int i=m+1;i<=n;i++){
			int k=(x*i_2+y*i_1+z)%1000000000+1;
			nint temp{k-i,i};
			pmx(temp);
			i_2=i_1;i_1=k;
		}
	}
	int ans=mx.back().a+1;
	int p=1;
	int i_2=0,i_1=0;
	for(int i=2;i<=n;i++){
		if(mx.back().t<i)mx.pop_back();
		nint temp;
		if(f==1)temp.a=d[i-1]-(i-1);
		else{
			if(i-1<=m){
				temp.a=d[i-1]-(i-1);
				i_2=i_1;i_1=d[i-1];
			}else{
				int k=(x*i_2+y*i_1+z)%1000000000+1;
				temp.a=k-(i-1);
				i_2=i_1;i_1=k;
			}
		}
		temp.a-=n;temp.t=i-1+n;
		pmx(temp);
		if(mx.back().a+i<ans){
			ans=mx.back().a+i;
			p=i;
		}
	}
	cout<<ans<<" "<<p;
	return 0;
}