自动搬运

查看原文

来自洛谷，原作者为

	Aventurine_stone （已AFO）愿人生的赌局，赢的总是我们。

搬运于2025-08-24 23:05:12，当前版本为作者最后更新于2024-10-17 20:01:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

1. 题目分析

题目简述：对于每一个人，找到离他最近且和他不是同一个国家的人。
不会有人用数据结构吧，那太复杂了，其实可以线性扫描的。

2. 题目做法

对于每个人，我们只需要记录在这个人前面与其不同国籍且最近的人，和在这个人后面与其不同国籍且最近的人。
首先要以位置为关键字进行排序，之后正反分别扫一遍，先将第一个位置的值存进数组，之后若国籍与数组中的国籍相同，则将其也存进数组，否则我们就找到了在这一边与这个数组内的人不同国籍且离他们最近的人，然后再将这个不同国籍的人放进空数组中。一直扫直到尽头即可。

3. 代码

#include<bits/stdc++.h>
using namespace std;
const int N=300010;
inline int read()
{
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9')
		c=getchar();
	while(c>='0'&&c<='9')
		x=(x<<1)+(x<<3)+c-'0',c=getchar();
	return x;
}
int n;
struct P{
	int id,c,x;
}a[N];
inline bool cmp(P a1,P a2)
{
	return a1.x<a2.x;
}
int l[N],r[N];
int c[N],cnt,t,ans[N];
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
		a[i]={i,read(),read()};
	sort(a+1,a+n+1,cmp);
	c[++cnt]=1;
	for(int i=2;i<=n;i++)
	{
		if(a[c[1]].c==a[i].c)
			c[++cnt]=i;
		else
		{
			while(cnt)
				r[c[cnt]]=i,cnt--;
			c[++cnt]=i;
		}
	}
	cnt=0;
	c[++cnt]=n;
	for(int i=n-1;i>=1;i--)
	{
		if(a[c[1]].c==a[i].c)
			c[++cnt]=i;
		else
		{
			while(cnt)
				l[c[cnt]]=i,cnt--;
			c[++cnt]=i;
		}
	}
	for(int i=1;i<=n;i++)
	{
		t=INT_MAX;
		if(l[i])
			t=a[i].x-a[l[i]].x;
		if(r[i])
			t=min(t,a[r[i]].x-a[i].x);
		ans[a[i].id]=t;
	}
	for(int i=1;i<=n;i++)
		printf("%d\n",ans[i]);
	return 0;
}