邻值查找-(模拟链表)

素颜马尾好姑娘i 2021-11-23 04:32 204阅读 0赞

问题：  
给定一个长度为 n 的序列 A 中的数各不相同。对于 A 中的每一个数 Ai，求：  
min1≤j<i|Ai−Aj|  
以及令上式取到最小值的 j（记为 Pi）。若最小值点不唯一，则选择使 Aj 较小的那个。

输入格式  
第一行输入整数n，代表序列长度。  
第二行输入n个整数A1…An,代表序列的具体数值，数值之间用空格隔开。

输出格式  
输出共n-1行，每行输出两个整数，数值之间用空格隔开。  
分别表示当i取2~n时，对应的min1≤j<i|Ai−Aj|和Pi的值。

数据范围  
n≤105 |Ai|≤109

输入样例：  
3  
1 5 3

输出样例：  
4 1  
2 1

思路：模拟一下链表，要做这题首先想到贪心，从第n个开始向前找，一直遍历到1，TLE。  
我们可以从小到大排个序，这样只需要找这个数的前后两个数做差取最小的就行了。

注意：存储的时候要存两个值，一个是数值，一个是坐标，使用pair，当然用结构体也没问题。  
模拟链表，链表需要两个指针head（前）和tail（后） 这里我们用 l 数组和 r 数组模拟，再开一个p数组记录原位置的数位于排完序后的哪里，5 4 3 2 1 1位于原来的第5个数， 排完序后1位于第1位。  
p\[5\]=1 表示原来的第5位现在是第1位。  
然后就比较大小，最最最最最重要的是，比较完后要把这个数给去掉，让两个指针数组连起来就行了。

代码：

#include<iostream>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int N=1e5;
    pair<int,int> a[N],ans[N];
    int l[N],r[N],p[N];
    int main() 
    {
    	int n;
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
    		cin>>a[i].first;
    		a[i].second=i;
    	}
    	sort(a+1,a+1+n);
    	
    	for(int i=1;i<=n;i++)
    	{
    		r[i]=i+1;
    		l[i]=i-1;
    		p[a[i].second]=i;
    	}
    	a[0].first=1e10;
    	a[n+1].first=1e10;
    	int j,right,left;
    	for(int i=n;i>1;i--)
    	{
    		j=p[i];
    		right=r[j];
    		left=l[j];
    		int lv=abs(a[j].first-a[left].first);
    		int rv=abs(a[j].first-a[right].first);
    		if(lv<=rv) ans[i]={lv,a[left].second};
    		else ans[i]={rv,a[right].second};
    		
    		r[left]=right;
    		l[right]=left;
    	}
    	
    	for(int i=2;i<=n;i++)
    	{
    		cout<<ans[i].first<<" "<<ans[i].second<<endl;
    	}
    	return 0;
    }