AcWing 136. Adjacent value lookup

AcWing 136. Neighbor search

Ideas

1. It's easy to think of sequence sorting , The difference between at least one of the left and right elements of the current element and the current element is the smallest in the whole sequence .

2. Then the topic needs to be found $mi{n}_{1\le j<i}|A_i-A_j|$ The smallest of all $A_j$ , It will be $A$ After sorting, adjacent subscripts may be larger than the current subscript .

3. To solve this problem, we need a two-way linked list , from $A$ The last element of the sequence begins to calculate , Delete the node directly after calculation , In the next calculation, there will be no adjacent points larger than the current subscript .

• $a$ The array represents the data field of the linked list , The node order of the linked list is $a$ After the array is in ascending order .
• $p$ Array quick get $A$ Sequence number $x$ The position of the number in the linked list .
• $l$ And $r$ The array represents the left and right node indexes of the linked list nodes .
• Then the left and right ends of the linked list have boundary problems , Just put two sentinels here .

#include<iostream>
#include<algorithm>
#include<cmath>
#define x first
#define y second
using namespace std;
typedef long long LL;
const int N = 100010;

pair<LL,int> a[N], ans[N];
int p[N],l[N],r[N];

int main(){
    
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    int n; cin>>n;
    for(int i = 1; i <= n; i++){
    
        cin>>a[i].x;
        a[i].y = i;
    }
    
    sort(a+1, a+1+n);
    a[0].x = a[n+1].x  = -4e9; // Put two sentinels to prevent border problems 
    for(int i = 1; i <= n; i++){
    
        l[i] = i-1, r[i] = i+1;
        p[a[i].y] = i; // Mapping position 
    }
    
    for(int i = n; i > 1; i--){
    
        int j = p[i], left = l[j], right = r[j];
        LL lv = abs(a[j].x - a[left].x);
        LL rv = abs(a[j].x - a[right].x);
        if(lv <= rv) ans[i] = {
    lv, a[left].y};
        else ans[i] = {
    rv, a[right].y};
        
        r[left] = right;
        l[right] = left;
    }

    for(int i = 2; i <= n; i++) cout<< ans[i].x << ' ' << ans[i].y << '\n';
    
    return 0;
}