$set做法$
#include <iostream>
#include <algorithm>
#include <set>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
const LL INF = 4e9;
int n;
set<PLL> s;
int main()
{
LL x;
scanf("%d%lld", &n, &x);
s.insert({INF, n + 1});
s.insert({-INF, 0});
s.insert({x, 1});
for (int i = 2; i <= n; i ++ )
{
scanf("%lld", &x);
LL ans = INF;
int id = INF;
auto t = s.upper_bound({x, n + 1});
t -- ;
ans = abs(x - t -> first);
id = t -> second;
t = s.lower_bound({x, 0});
if (t -> first - x < ans) //取更小的
{
ans = abs(x - t -> first);
id = t -> second;
}
printf("%lld %lld\n", ans, id);
s.insert({x, i});
}
return 0;
}
$链表$
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PLI;
const int N = 100010;
const LL INF = 4e9;
int n;
int l[N], r[N], p[N];
PLI a[N], ans[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%lld", &a[i].first);
a[i].second = i;
}
sort(a + 1, a + n + 1);
a[0].first = -INF, a[n + 1].first = INF;
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]; //对每一个i 找到链表下标
int left = l[j], right = r[j]; //链表前驱后继
LL lv = abs(a[j].first - a[left].first);
LL rv = abs(a[right].first - a[j].first);
if (lv <= rv) ans[i] = {lv, a[left].second};
else ans[i] = {rv, a[right].second};
l[right] = left, r[left] = right;
}
for (int i = 2; i <= n; i ++ )
printf("%d %d\n", ans[i].first, ans[i].second);
return 0;
}
$单调栈$
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PLI;
const int N = 100010;
const LL INF = 4e9;
int n;
int l[N], r[N], p[N];
PLI a[N];
int q[N], tt;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%lld", &a[i].first);
a[i].second = i;
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i ++ )
p[a[i].second] = i;
a[0].first = -INF, a[n + 1].first = -INF;
q[0] = 0; //哨兵不加也可以 因为 0 n + 1默认是0 第一个算错不影响答案
for (int i = 1; i <= n; i ++ )
{
int v = a[i].second;
while (a[q[tt]].second >= v) tt -- ;
l[i] = q[tt];
q[ ++ tt] = i;
}
tt = 0;
q[0] = 0;
for (int i = n; i >= 1; i -- )
{
int v = a[i].second;
while (a[q[tt]].second >= v) tt -- ;
r[i] = q[tt];
q[ ++ tt] = i;
}
for (int i = 2; i <= n; i ++ )
{
int j = p[i], left = l[j], right = r[j];
//printf("%d %d %d\n", j, left, right);
LL lv = abs(a[j].first - a[left].first);
LL rv = abs(a[right].first - a[j].first);
if (lv <= rv) printf("%lld %d\n", lv, a[left].second);
else printf("%lld %d\n", rv, a[right].second);
}
return 0;
}