首页 / 算法 / 《算法竞赛进阶指南》1.3链表
《算法竞赛进阶指南》1.3链表
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了《算法竞赛进阶指南》1.3链表,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1473字,纯文字阅读大概需要3分钟。
内容图文
136. 邻值查找
给定一个长度为 n 的序列 A,A 中的数各不相同。对于 A 中的每一个数 Ai,求:
min 1≤j<i |Ai?Aj|
以及令上式取到最小值的 j(记为 Pi)。若最小值点不唯一,则选择使 Aj较小的那个。
输入格式
第一行输入整数n,代表序列长度。
第二行输入n个整数A1…An,代表序列的具体数值,数值之间用空格隔开。
输出格式
输出共n-1行,每行输出两个整数,数值之间用空格隔开。
分别表示当i取2~n时,对应的min1≤j<i|Ai?Aj|和Pi的值。
数据范围
n≤10 ^5,|Ai|≤10 ^9
输入样例:
3
1 5 3
输出样例:
4 1
2 1
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PII; //数值 和下标
const int N = 100010;
int n;
int p[N], l[N], r[N]; //p[N]第n个点的位置,双向链表前驱后继
PII a[N], ans[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> a[i].first;
a[i].second = i;
}
sort(a + 1, a + 1 + n);
a[0].first = 1e9, a[n + 1].first = -1e9; //两个哨兵 不用处理边界 让开头和结尾 不影响结果
for(int i = 1; i <= n; i++) //从前往后遍历数组,建立链表
{
l[i] = i - 1, r[i] = i + 1;
p[a[i].second] = i; //记录每个点在双向链表的位置
}
for(int i = n; i > 1; i--)
{
int j = p[i], left = l[j], right = r[j];
int lv = abs(a[j].first - a[left].first);
int rv = abs(a[right].first - a[j].first);
if(lv <= rv) ans[i] = {lv, a[left].second};
else ans[i] = {rv, a[right].second}; //左右两边相等,选左边的数
// else ans[i] = {lv, min(a[left].second, 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;
}
内容总结
以上是互联网集市为您收集整理的《算法竞赛进阶指南》1.3链表全部内容,希望文章能够帮你解决《算法竞赛进阶指南》1.3链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。