CH1301 邻值查询(链表)(SET容器)
程序员文章站
2024-03-06 20:28:38
...
题目
给定一个长度为 n(n<=10^5)的序列 A,A 中的数各不相同。对于 A 中的每一个数 Ai,求: 以及令上式取到最小值的 j(记为 Pi)。若最小值点不唯一,则选择使 Aj 较小的那个。
题解1
离线做法:链表+排序
先把所有数按顺序排序,然后依次插入链表。这时一个节点的prev和next分别对应它的前驱和后继。我们从后往前枚举每个数,再找到它的邻值后,便把它删了。因为它不能影响i-1之前的数的前驱和后继,这也是要从后往前枚举的原因。
总结
排序+链表 可以解决支持删除的求一个数的前驱和后继的问题。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
int n;
int p[maxn],w[maxn];
struct node
{
int val,pos,prev,next;
}a[maxn];int tail;
bool cmp(int p1,int p2)
{
return w[p1]<w[p2];
}
void ins(int val,int pos)//在链表的末端插入一个值为val,位置为pos的数
{
tail++;
a[tail].val=val;a[tail].pos=pos;
a[tail].prev=tail-1;
a[tail-1].next=tail;
}
void remove(int p)//删除a[p]
{
a[p].pos=-1;
a[a[p].prev].next=a[p].next;
a[a[p].next].prev=a[p].prev;
}
int zhizhen[maxn];//zhizhen[i]表示原序列中第i个数,所映射的链表节点的编号
int as1[maxn],as2[maxn];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
p[i]=i;
}
sort(p+1,p+n+1,cmp);
tail=1;
a[1].val=w[p[1]];
a[1].pos=p[1];
zhizhen[p[1]]=1;
for(int i=2;i<=n;i++)
{
ins(w[p[i]],p[i]);
zhizhen[p[i]]=tail;
}
for(int i=n;i>=2;i--)
{
int mn=2e9,mx=2e9;
if(a[zhizhen[i]].prev!=0) mn=abs(w[i]-a[a[zhizhen[i]].prev].val);
if(a[zhizhen[i]].next!=0) mx=abs(w[i]-a[a[zhizhen[i]].next].val);
if(mn<=mx)//若最小值点不唯一,则选择使 Aj 较小的那个
{
as1[i]=mn;
as2[i]=a[a[zhizhen[i]].prev].pos;
}
else if(mn>mx)
{
as1[i]=mx;
as2[i]=a[a[zhizhen[i]].next].pos;
}
remove(zhizhen[i]);
}
for(int i=2;i<=n;i++) printf("%d %d\n",as1[i],as2[i]);
return 0;
}
题解2
在线:set容器
什么“前驱”、“后继”,不都是学splay时提出的术语吗?这题的确是splay裸题!爱打splay就打splay吧,反正我用STL的set容器。
代码
#include<set>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
struct A
{
int a,p;
bool operator<(A a1)const
{
return a<a1.a;
}
};
set<A> s;
int main()
{
int n,x;
scanf("%d",&n);
scanf("%d",&x),s.insert((A){x,1});
for(int i=2;i<=n;i++)
{
scanf("%d",&x);
set<A>::iterator ir=s.lower_bound((A){x,0}),il=ir;il--;
if(ir==s.end())
{
printf("%d %d\n",x-il->a,il->p);
}
else if(ir==s.begin())
{
printf("%d %d\n",ir->a-x,ir->p);
}
else if(x-il->a<=ir->a-x)
{
printf("%d %d\n",x-il->a,il->p);
}
else
{
printf("%d %d\n",ir->a-x,ir->p);
}
s.insert((A){x,i});
}
return 0;
}