给定一个环序列 求 \(max\{ a[i]+a[j]+min(i-j,n-(i-j) ) \} ,i>j\)
环上距离最大问题 对于这种既要考虑顺时针,也要考虑逆时针的时候,可以考虑复制环接在后面 这样在两个环的交界处就相当于不同方向转移
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N=2e6+10;
int read()
{
int x=0,f=0,c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return f?-x:x;
}
int a[N],n,ans;
deque<int> q;
int main()
{
n=read();
for(int i=1;i<=n;i++) a[i]=a[i+n]=read();
q.push_back(1);
for(int i=2;i<=n+n/2;i++)
{
while(q.size()&&i-q.front()>n/2) q.pop_front();
ans=max(ans,a[i]+a[q.front()]+i-q.front());
while(q.size()&&a[i]-i>a[q.back()]-q.back()) q.pop_back();
q.push_back(i);
}
printf("%d\n",ans);
return 0;
}
这里有个细节: 长度不能超过n/2,否则就不满足距离的定义