P11200 [JOIG 2024] 座席 2 / Seats 2

题目描述

今年，JOI 国将主办 IOI（国际信息学奥林匹克竞赛）。届时将有 $N$ 名选手参赛，编号从 $1$ 到 $N$。

每位选手的国籍由一个介于 $1$ 和 $10^9$ 之间的整数表示：选手 $i(1\le i\le N)$ 来自国家 $C_i$。保证 $N$ 个选手的国籍不完全相同（即存在 $i\ne j(1\le i,j\le N)$ 使得 $C_i\ne C_j$）。

选手的座位排成一条直线，选手 $i(1\le i\le N)$ 的座位在 $X_i$ 处。选手 $i(1\le i\le N)$ 和选手 $j(1\le j\le N)$ 之间的座位距离为 $|X_i-X_j|$。

每个选手都想知道在与其他选手交流时，与离自己最近的异国选手的座位距离。

给定每个选手的国籍和座位位置，请为每个选手 $i(1\le i\le N)$ 求出与其来自不同国家的选手中，座位离选手 $i$ 最近的选手与 $i$ 的座位距离。

输入格式

第一行输入一个整数 $N$。

接下来 $N$ 行，每行输入两个整数 $C_i,X_i$。

输出格式

输出 $N$ 行，第 $i$ 行输出一个整数，表示座位离选手 $i$ 最近的选手与 $i$ 的座位距离。

输入输出样例 #1

输入 #1

3
2 5
1 1
1 2

输出 #1

3
4
3

输入输出样例 #2

输入 #2

5
1 1
2 4
2 14
3 10
2 2

输出 #2

1
3
4
4
1

输入输出样例 #3

输入 #3

3
1 1
2 1
1 1

输出 #3

0
0
0

说明/提示

【样例解释 #1】

• 选手 $1$ 来自国家 $2$，选手 $2,3$ 和他 / 她来自不同国家。在这些选手中，与选手 $1$ 座位距离最小的是选手 $3$，座位距离为 $3$。因此，答案为 $3$；
• 选手 $2$ 来自国家 $1$，选手 $1$ 是唯一和他 / 她来自不同国家的选手。选手 $2$ 和选手 $1$ 之间的座位距离为 $4$；
• 选手 $3$ 来自国家 $1$，选手 $1$ 是唯一和他 / 她来自不同国家的选手。选手 $3$ 和选手 $1$ 之间的座位距离为 $3$。

该样例满足子任务 $1,2,3$ 的限制。

【样例解释 #2】

该样例满足子任务 $1,2,3$ 的限制。

【样例解释 #3】

该样例满足子任务 $1,2,3$ 的限制。

【数据范围】

• $2\le N\le 3\times 10^5$；
• $1\le C_i\le 10^9(1\le i\le N)$ 且 $C_i$ 不完全相同；
• $1\le X_i\le 10^9(1\le i\le N)$。

【子任务】

1. （$20$ 分）$N\le 1000$；
2. （$40$ 分）$C_i\le 10(1\le i\le N)$；
3. （$40$ 分）无附加限制。

C++实现

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n;
int dis[N];
struct Node{
int num,c,x;
}f[N];
bool cmp(Node a,Node b){
return a.x<b.x;
}
int main(){
memset(dis,0x3f,sizeof(dis));
cin>>n;
for(int i=1;i<=n;i++){
cin>>f[i].c>>f[i].x;
f[i].num=i;
}
sort(f+1,f+n+1,cmp);
for(int i=2;i<=n;i++){
if(f[i].c!=f[i-1].c){
dis[f[i].num]=min(dis[f[i].num],f[i].x-f[i-1].x);
}
else{
dis[f[i].num]=min(dis[f[i-1].num]+f[i].x-f[i-1].x,dis[f[i].num]);
}
}
for(int i=n-1;i>=1;i–){
if(f[i].c!=f[i+1].c){
dis[f[i].num]=min(dis[f[i].num],f[i+1].x-f[i].x);
}
else{
dis[f[i].num]=min(dis[f[i+1].num]+f[i+1].x-f[i].x,dis[f[i].num]);
}
}
for(int i=1;i<=n;i++){
cout<<dis[i]<<“\n”;
}
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容