| 题目名称 | 1226. 班级聚会 |
|---|---|
| 输入输出 | reunion.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 5 |
| 题目来源 |
 王者自由
于2012-10-26加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：5， 提交：16， 通过率：31.25% | ||||
 再见 |
100 | 0.022 s | 2.10 MiB | C++ |
 zhengtn03 |
100 | 0.022 s | 5.46 MiB | C++ |
 ConanQZ |
100 | 0.054 s | 1.31 MiB | Pascal |
|
ConanQZ |
100 | 0.054 s | 1.31 MiB | Pascal |
 Makazeu |
100 | 0.130 s | 1.27 MiB | C++ |
 我想 |
80 | 0.001 s | 0.22 MiB | Pascal |
|
ConanQZ |
80 | 0.007 s | 0.28 MiB | Pascal |
|
ConanQZ |
80 | 0.054 s | 1.31 MiB | Pascal |
 Cloud |
80 | 0.080 s | 2.67 MiB | C++ |
|
Makazeu |
80 | 0.107 s | 3.34 MiB | C++ |
| 关于 班级聚会 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
這題的第4組數據有多解。如果多解了，輸出最靠近莫斯科的城市名。 我用的帶權中位數，時間複雜度O(N)。
Makazeu
2012-10-27 16:51
3楼
| ||||
|
带权中位数
Makazeu
2012-10-27 01:48
2楼
| ||||
|
妥妥的N^2暴力= =
| ||||
【问题描述】
毕业25年以后，我们的主人公开始准备同学聚会。打了无数电话后他终于搞到了所有同学的地址。他们有些人仍在本城市，但大多数人分散在其他的城市。不过，他发现一个巧合，所有地址都恰好分散在一条铁路线上。他准备出发邀请但无法决定应该在哪个地方举行宴会。最后他决定选择一个地点，使大家旅行的花费和最小。
不幸的是，我们的主人公既不擅长数学，也不擅长计算机。他请你帮忙写一个程序，根据他同学的地址，选择聚会的最佳地点。
【输入】
输入文件的每一行描述了一个城市的信息。
首先是城市里同学的个数，紧跟着是这个城市到Moscow（起点站）的距离（km），最后是城市的名称。最后一行描述的总是Moscow，它在铁路线的一端，距离为0。城市数不超过50000个。
【输出】
聚会地点城市名称和旅行费用（单程），两者之间用一空格隔开。每km花费一个卢布。
【样例】
reunion.in
7 9289 Vladivostok
5 8523 Chabarovsk
3 5184 Irkutsk
8 2213 Yalutorovsk
10 0 Moscow
reunion.out
Yalutorovsk 112125