RYIP在线题库
首 页   >   习题练习   >   提交
Problem2075--游乐场(park)

2075: 游乐场(park)

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

【 Description 】

OI 游乐场里有 m 个娱乐项目,分布在一条道路旁,第 i 个项目的坐标是 xi,费用是 ci。
有 n 个学生来到了游乐场,第 j 个学生目前处于坐标 yj。因为每个学生都想先去离自己较近且较便宜的项目开始游玩,所以第 j 个学生会选择使得 ∣xi−yj∣+ci 最小的项目开始游玩。
对于每个学生,输出 ∣xi−yj∣+ci的最小值。


【 Input 】

从文件 park.in 中读入数据。
第一行两个整数 n,m,分别表示学生数目和项目数目。
第二行 n 个整数,表示每个学生目前的坐标 yj。
第三行 m 个整数,表示每个娱乐项目的坐标 xi。
第四行 m 个整数,表示每个娱乐项目的费用 ci。

【 Output 】

输出到文件 park.out 中。

输出一行 n 个整数,表示每个学生对应的最小值。


【 Sample Input 】

4 4
2 3 4 5
1 7 9 15
0 0 0 0

【 Sample Output 】

1 2 3 2

【HINT】

2023 合肥市经开区初中

数据范围

  • 对于 35% 的数据,1≤n,m≤1000
  • 对于另外 15%的数据,对于所有的 i,有 ci=0
  • 对于另外 20% 的数据,yj<xi恒成立。
  • 对于 100%的数据,1≤n,m≤1051≤xi,yj≤1090≤ci≤109
  • 数据保证 xi,yj各自按坐标递增顺序给出,不存在一个坐标同时有学生和娱乐项目。



【 Source/Category 】

top TX