自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 22:54:32，当前版本为作者最后更新于2024-01-24 00:29:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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