APCS 325 習題Q-3-13 X差值範圍內的最大Y差值

#include<iostream>
#include<algorithm>
#include<cmath> 
#include<deque>
#include<fstream>
using namespace std;

struct posion{
    int x,y;
};

bool cmp(posion a,posion b){
    return a.x<b.x;
}

posion seq[200010];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    //ifstream fi;
    //fi.open("Q_3_13_5.in");
    int n,L;
    cin>>n>>L;
    //fi>>n>>L;
    for(int i=0;i<n;i++){
        cin>>seq[i].x;
        //fi>>seq[i].x;
    }
    for(int i=0;i<n;i++){
        cin>>seq[i].y;
        //fi>>seq[i].y;
    }
    sort(seq,seq+n,cmp);

    int best=0;
    deque<int> max,min;
    for(int i=0,j=0;i<n;i++){
        while(!max.empty() && seq[i].x-seq[max.back()].x>L)
            max.pop_back();
        while(!min.empty() && seq[i].x-seq[min.back()].x>L)
            min.pop_back();
        while(!max.empty() && seq[i].y>seq[max.back()].y)
            max.pop_front();
        while(!min.empty() && seq[i].y<seq[min.back()].y)
            min.pop_front();
        max.push_front(i);
        min.push_front(i);

        if(!max.empty() && !min.empty() && 
            abs(seq[max.back()].y-seq[min.back()].y)>best){
                best=abs(seq[max.back()].y-seq[min.back()].y);
            }
    }
    cout<<best;
    return 0;
}

出處:https://judge.tcirc.tw/ShowProblem?problemid=d037

AC 44ms

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *