P11200 题解

Aventurine_stone · 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;
}