UC知道pascal 一题
来源：百度知道 编辑：UC知道 时间：2024/05/19 02:04:51
毕业25年以后，我们的主人公开始准备同学聚会。打了无数电话后他终于搞到了所有同学的地址。他们有些人仍在本城市，但大多数人分散在其他的城市。不过，他发现一个巧合，所有地址都恰好分散在一条铁路线上。他准备出发邀请但无法决定应该在哪个地方举行宴会。最后他决定选择一个地点，使大家旅行的花费和最小。(城市个数小于1001）
不幸的是，我们的主人公既不擅长数学，也不擅长计算机。他请你帮忙写一个程序，根据他同学的地址，选择聚会的最佳地点。
【输入】
输入文件的每一行描述了一个城市的信息。
首先是城市里同学的个数，紧跟着是这个城市到Moscow（起点站）的距离（km），最后是城市的名称。最后一行描述的总是Moscow，它在铁路线的一端，距离为0。
【输出】
聚会地点城市名称和旅行费用（单程），两者之间用一空格隔开。每km花费一个卢布。
【样例】
输入： 输出：
7 9289 Vladivostok Yalutorovsk 112125
5 8523 Chabarovsk
3 5184 Irkutsk
8 2213 Yalutorovsk
10 0 Moscow
type rec=record
n,x:int64;
m:ansistring;
end;
var i,tot:int64; s:ansistring; j:longint;
date,da:array[0..10100] of rec;
procedure find(a:longint);
var min:int64;l:longint;
begin
min:=0;
for l:=1 to i do
da[l].x:=abs(date[l].x-date[a].x);
for l:=1 to i do
min:=min+date[l].n*da[l].x;
if min<tot then
begin
不幸的是，我们的主人公既不擅长数学，也不擅长计算机。他请你帮忙写一个程序，根据他同学的地址，选择聚会的最佳地点。
【输入】
输入文件的每一行描述了一个城市的信息。
首先是城市里同学的个数，紧跟着是这个城市到Moscow（起点站）的距离（km），最后是城市的名称。最后一行描述的总是Moscow，它在铁路线的一端，距离为0。
【输出】
聚会地点城市名称和旅行费用（单程），两者之间用一空格隔开。每km花费一个卢布。
【样例】
输入： 输出：
7 9289 Vladivostok Yalutorovsk 112125
5 8523 Chabarovsk
3 5184 Irkutsk
8 2213 Yalutorovsk
10 0 Moscow
type rec=record
n,x:int64;
m:ansistring;
end;
var i,tot:int64; s:ansistring; j:longint;
date,da:array[0..10100] of rec;
procedure find(a:longint);
var min:int64;l:longint;
begin
min:=0;
for l:=1 to i do
da[l].x:=abs(date[l].x-date[a].x);
for l:=1 to i do
min:=min+date[l].n*da[l].x;
if min<tot then
begin
...错了错了，不是图论题，因为完全可以转化为在一个平面上，因此找中位数所在位置为正解
我想复杂了，忽略了是一共就一条铁路线，而不是k条铁路线不同方向，幸好这不是NOIP09啊..
采用广义深度搜索。
找到人数的中间点作为目标
再做统计算总花费
不用回溯，用数学方法，
I为头指针，J为尾指针
直到I>J为止
使用广度优先搜索，可节省时间，不过要注意下空间