微商做网站,网页qq官网,上百度推广 免费做网站,上饶网站开发邻值查找
给定一个长度为 n 的序列 A#xff0c;A 中的数各不相同。对于 A 中的每一个数 Ai#xff0c;求#xff1a; min1≤ji|Ai−Aj|
以及令上式取到最小值的 j#xff08;记为 Pi#xff09;。若最小值点不唯一#xff0c;则选择使 Aj 较小的那个。
输入格式 …邻值查找
给定一个长度为 n 的序列 AA 中的数各不相同。对于 A 中的每一个数 Ai求 min1≤ji|Ai−Aj|
以及令上式取到最小值的 j记为 Pi。若最小值点不唯一则选择使 Aj 较小的那个。
输入格式 第一行输入整数n代表序列长度。 第二行输入n个整数A1…An,代表序列的具体数值数值之间用空格隔开。
输出格式 输出共n-1行每行输出两个整数数值之间用空格隔开。 分别表示当i取2~n时对应的min1≤ji|Ai−Aj|和Pi的值。
数据范围 n≤105,|Ai|≤109 输入样例 3 1 5 3 输出样例 4 1 2 1 这里提供一个双向链表的写法 EXAMPLE IN PUT 10 4 5 6 1 2 3 7 8 9 10
OUTPUT 1 1 1 2 3 1 1 4 1 5 1 3 1 7 1 8 1 9
具体思路如下图 Befor
value45612378910id12345678910
我们先标记初始值的id
Sorted 我们在前后设置了两个哨兵。
value∞12345678910∞id04561237891011
然后从后面枚举
value∞12345678910∞id04561237891011
得到 相邻最小可选的 id——9 11 ———————value—1 ∞ 我们选出最佳的 id 是 9 . 如图我们删去这个元素把这个删去元素的前后相连。 不断重复如上操作最后到只剩一个元素。
#includeiostream
#includealgorithm
#includecstdio
using namespace std;
const int N 1e5 10;
int p[N], l[N], r[N], n;
pairint, int a[N], ans[N];
int main() {scanf(%d, n);for(int i 1; i n; i) {scanf(%d, a[i].first);a[i].second i;}a[0].first 1e9;a[n 1].first -1e9;sort(a 1, a n 1);for(int i 1; i n; i) {p[a[i].second] i;l[i] i - 1;r[i] i 1;}for(int i n; i 2; i--) {int pos p[i];int Left l[pos];int Right r[pos];int vl abs(a[pos].first - a[Left].first);int vr abs(a[pos].first - a[Right].first);if(vl vr) {ans[i].first vl;ans[i].second a[Left].second;}else {ans[i].first vr;ans[i].second a[Right].second;}r[Left] Right;l[Right] Left; }for(int i 2; i n; i)printf(%d %d\n, ans[i].first, ans[i].second);return 0;
}
