XnMatrix vim复制 Pytorch 父子元素 string express perl mysqli jwt vue组件注册 jquery第一个子元素 大数据驾驶舱 linux源码在线阅读 python查看数据类型 svn默认安装路径 div外边距 matlab跳出for循环 ai如何导出矢量图 java 注解 python基础 python的str python怎么配置环境 java中数据类型 java怎么使用 java怎么获取当前时间 linux教程 linux装机 p2pover 谷歌地球打不开 linux操作系统原理 小米5c拆机 pr缩放 程序员面试宝典 键盘指法练习软件 在线手册 list删除指定元素 x64dbg 鬼灵战马 冰冠堡垒单刷路线 平均值符号怎么输入
当前位置: 首页 > 学习教程  > 编程语言

邻值查找

2021/2/13 17:12:11 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

题目(邻值查找) 给定一个长度为 n 的序列 A&#xff0c;A 中的数各不相同。对于 A 中的每一个数 Ai&#xff0c;求&#xff1a; min|Ai−Aj|&#xff08;1≤j<i&#xff09;以及令上式取到最小值的 j&#xff08;记为 Pi&#xff09;。若最小值点不唯一&#xff0c;则选择使…

题目(邻值查找)

给定一个长度为 n 的序列 A,A 中的数各不相同。对于 A 中的每一个数 Ai,求:
min|Ai−Aj|1≤j<i)以及令上式取到最小值的 j(记为 Pi)。若最小值点不唯一,则选择使 Aj 较小的那个。
输入格式

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

输出格式

输出共n-1行,每行输出两个整数,数值之间用空格隔开。

分别表示当i取2~n时,对应的min|Ai−Aj|1≤j<i)和Pi的值。

数据范围

n≤1e5,
|Ai|≤1e9

输入样例:

3
1 5 3

输出样例:

4 1
2 1

思路:

将原序列排序后串成一个链表,本题麻烦就麻烦在链表编号和原序列编号,以及左指针右指针之间的关系。而且得从原序列中的第n个元素开始往前找,不然就很麻烦,之前就是从中间开始往两边找,极其麻烦。

代码:

#include<iostream>
#include<algorithm>
#include<climits>
#include<cmath>
using namespace std;
typedef pair<int,int> PII;
const int N=100010;
PII a[N],res[N];//a[N]存储原序列,res[N]存储答案
int L[N],R[N],pos[N];//链表左指针右指针以及链表中元素的位置与其原序列中的位置对应关系
int r;//计数器
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+n+1);
    a[0].first=INT_MIN;
    a[n+1].first=INT_MAX;//避免处理边界问题
    for(int i=1;i<=n;i++)
    {
        pos[a[i].second]=i;
        L[i]=i-1;
        R[i]=i+1;
    }//将链表中位置关系左指针右指针对应起来
    int position,left1,right1;
    for(int i=n;i>=2;i--)//本题是从第n个元素开始找,这样就避免了从中间开始双向找的麻烦,我之前就是双向找然后情况太多debug不出来啊啊啊
    {
        position=pos[i];
        left1=L[position];
        right1=R[position];
        if(abs(a[position].first-a[left1].first)<=abs(a[right1].first-a[position].first)) 
        {
            res[++r].first=abs(a[position].first-a[left1].first);
            res[r].second=a[left1].second;
        }
        else  
        {
            res[++r].first=abs(a[right1].first-a[position].first);
            res[r].second=a[right1].second;
        }
        R[left1]=right1;
        L[right1]=left1;//删除节点
    }
    for(int i=r;i>=1;i--)
    cout<<res[i].first<<" "<<res[i].second<<endl;//倒着从2-n输出答案
    return 0;
}

本题还有一种方法但是我没学,见书P61


本文链接: http://www.dtmao.cc/news_show_700087.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?