AcWing136 逆向思维、链表

AcWing136临值查找 链表做法

题目大意：

??就是从一个数往前找一个和他之差的绝对值最小的数。

思路

??要是我们能把数从小到大排序，这样找和他绝对值之差最小的数就只用拿他和相邻的两项之间比较就行了。
??因为题目说的是往前找，那么我们从末尾开始找，上面相当与提供了一种可以快速找到符合要求的“相邻数”的表，然后根据上面那个提供的“相邻数”表找到的符合要求的与这个数进行比较。
??在比较得到答案之后，因为是从后往前找的，把那个数删去。这样那个数相邻的两个数搜索时就不会找到他。快速删去就要用到链表了。对那两个相邻的数来说，那个删去的数对答案没有贡献。因为是从后往前找的。这样相邻的数在考虑他们的相邻的数的时候会越过那个被删去的数。
??然后又考虑位置倒数第二的数。这样依次考虑完所有的数。

实现思路：

??可以对初始数组进行排序，再记录原始序列中每个数的位置。举个例子来说：
假设A等于5，原始序列A为

对A进行带下标排序：

??注意：这里抽象一点的思考1，2，3，4，5只是表示大小关系，而不指具体的1，2，3，4，5。比如5表示最大的数，也就是第5小的数，1表示最小的数，也就是第1小的数。
??然后用一个b数组来把大小、位置关系记录下来。举个例子：比如b[5]=2的意思就是原来第2小的数在5,也就是最后一个的位置上。怎么记录，可以看出用\(b[a[i].second]=i\)就可以记录。

??然后把那个数删掉之后的对应关系：

其中这种链接关系用链表实现，可以快速找到前驱、后继。

??最后，为了方便用一个很小的数和一个很大的数在两边充当“哨兵”，取出n项，保存答案就行了。
??时间复杂度:\(O(nlogn)\)

代码：

#include <ctime>
#include <cstdlib>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cstdio>
#include<string>
#include<string.h>
#include<list>
#include<queue>
#include<sstream>
#include<vector>
#include <cassert>   // assert
#include<set>
#include<map>
#include<deque>
#include<stack>
using namespace std;
#define debug(x) cout<<"###"<<x<<"###"<<endl;
const int INF=0x3f3f3f3f,mod=1e9,Maxn=1e5;
const double eps=1e-8;
typedef long long ll;
//list<ll> lst;
pair<ll,int> a[Maxn+5];
int b[Maxn+5],L[Maxn],R[Maxn];

bool cmp(pair<ll,int> c,pair<ll,int> d){
    return c.first<d.first;
}
pair<ll,int> ans[Maxn+5];
int main(){
    //init();
    int n;
    cin>>n;
    a[0].first=1ll*INF*100;
    a[0].second=0;
    a[n+1].first=1ll*INF*100;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i].first);
        a[i].second=i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        b[a[i].second]=i;//b数组
    }
    for(int i=1;i<=n;i++){
        L[i]=i-1;
        R[i]=i+1;//链接.L表示i位置左边的位置。同理R
    }
    for(int i=n;i>1;--i){
        ll lv=a[L[b[i]]].first;//找到左边的数
        ll rv=a[R[b[i]]].first;//找到右边的数
        ll v=a[b[i]].first;//考虑的数
        if(abs(lv-v)>abs(rv-v)){//取右边
            ans[i].first=abs(rv-v);
            ans[i].second=a[R[b[i]]].second;//保存答案
        }
        else if(abs(lv-v)<abs(rv-v)){//取左边
            ans[i].first=abs(lv-v);
            ans[i].second=a[L[b[i]]].second;
        }
        else{
            ans[i].first=abs(lv-v);
            if(rv>lv){
                ans[i].second=a[L[b[i]]].second;
            }
            else{
                ans[i].second=a[R[b[i]]].second;
            }
        }
        R[L[b[i]]]=R[b[i]];//删除那个数
        L[R[b[i]]]=L[b[i]];
    }
    for(int i=2;i<=n;++i){
        printf("%lld %d\n",ans[i].first,ans[i].second);
    }
}

《算法竞赛进阶指南》Acwing136 临值查找 链表做法

原文：https://www.cnblogs.com/Kamar/p/14224176.html