传送门

思路：

　　遇到一个环，用正常人类的思想就先把环从中间截断然后将其补成2*n长度的链。环上的最小距离换到链上就是i以n/2为半径范围内的点(画图肉眼可见)。由于两个点是等价的，所以我们考虑有序对(i,j){1<=j<i<=2*n&&i-j<=n/2}。

　　题目要求最大的a[i]+a[j]+dis(i,j)。在上述条件下，dis(i,j)=i-j。那么就是要求a[i]+a[j]+i-j，只要枚举i，得到最大的a[j]-j就好了，考虑j的取值范围[i-n/2,i-1]，用单调栈维护a[i]-j。

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+;

int a[*maxn],q[*maxn],tail,head,ans;

int main()

{

    int n;scanf("%d",&n);

    for(int i=;i<=n;i++)        scanf("%d",&a[i]);

    for(int i=+n;i<=*n;i++)    a[i]=a[i-n];

    int c=n/;

    for(int i=;i<=c;i++){

        while(tail&&a[q[tail]]-q[tail]<=a[i]-i)

            tail--;

        q[++tail]=i;

    }

    head=;

    ans=a[c+]+c+-q[head]+a[q[head]];

    for(int i=;i<=n;i++){

        int id=c-+i;

        while(head<=tail&&q[head]<i)    head++;

        while(tail>=head&&a[q[tail]]-q[tail]<=a[id]-id)    tail--;

        q[++tail]=id;

        ans=max(ans,a[id+]+id+-q[head]+a[q[head]]);

    }

    cout<<ans<<endl;

}

巴特西

CH5501 环路运输(单调栈)

传送门

思路：

最新文章

热门文章