hdu 5261 촉 도 난 단조 로 운 대열

제목: 한 원주 가 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
#include
#include
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(frontn) front++;

            if(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((txqs[rear-1]) rear--;
            q[rear]=i;
            qs[rear] = h[i]-(ll)r*i;
            rear++;
        }
        printf("Case #%d:
",++cas);
        printf("%d %d
",ax,ay);
    }
    return 0;
}