题目：一个圆周被均匀分成n个点，每个点有一个高度h[i]，定义两个点的距离是dis(i,j) = h[i] + h[j] + (劣弧i，j).问最长距离的点对，要求字典序最小。
单调队列：因为是圆周，要先把圆周变成链，倍增即可。在2n的链上，维护一个 h[i]-r*i 的单调递减队列，控制队列元素个数<=n/2，，每次加进一个元素更新一次答案。
为什么要维护h[i]-r*i的递减队列呢？因为革更新答案时 是用h[i]+r*i + h[q[front]] – r*q[front] .
代码：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int N = 1e5+10;typedef long long ll;int n;ll q[N*5],qs[N*5],h[N*2],r;int main(){int T,cas=0;cin >> T;ll ans=0;int ax,ay;while(T–){scanf("%d%I64d",&n,&r);ll ans=0;int ax=n,ay=n;for(int i=1;i<=n;i++){scanf("%I64d",&h[i]);h[i+n] = h[i];}int front=0, rear = 0;for(int i=1;i<=2*n;i++){while(front<rear && (i-q[front])*2>n) front++;if(front<rear &&(i-q[front])*2<=n && h[i]+(ll)r*i+qs[front]>=ans){if(h[i]+(ll)r*i+qs[front]>ans){int tx,ty;ans = h[i]+(ll)r*i+qs[front];tx = q[front]; ty = i;if(tx>n) tx-=n;if(ty>n) ty-=n;if(tx>ty) ax=ty , ay=tx;else ax=tx , ay=ty;}else if(h[i]+(ll)r*i+qs[front]==ans){int tx,ty;tx = q[front]; ty = i;if(tx>n) tx-=n;if(ty>n) ty-=n;if(tx>ty) swap(tx,ty);if((tx<ax)||(tx==ax&&ty<ay)){ax = tx , ay = ty;}}}while(front<rear && h[i]-(ll)r*i>qs[rear-1]) rear–;q[rear]=i;qs[rear] = h[i]-(ll)r*i;rear++;}printf("Case #%d:\n",++cas);printf("%d %d\n",ax,ay);}return 0;}
希望你灰暗的心情在此刻明亮起来，去迎接美好的明天!
