题目描述
毕业 25 年以后, 我们的主人公开始准备同学聚会. 打了无数电话后他终于搞到了所有同学的地址. 他们有些人仍在本城市, 但大多数人分散在其他的城市. 不过, 他发现一个巧合, 所有地址都恰好分散在一条铁路线上. 他准备出发邀请但无法决定应该在哪个地方举行宴会. 最后他决定选择一个地点, 使大家旅行的花费和最小.
不幸的是, 我们的主人公既不擅长数学, 也不擅长计算机. 他请你帮忙写一个程序, 根据他同学的地址, 选择聚会的最佳地点. 花费相同时优先取靠近莫斯科的城市.
输入格式
输入文件的每一行描述了一个城市的信息.
首先是城市里同学的个数, 紧跟着是这个城市到 Moscow(起点站) 的距离 (km), 最后是城市的名称. 最后一行描述的总是 Moscow, 它在铁路线的一端, 距离为 0.
输出格式
聚会地点城市名称和旅行费用 (单程), 两者之间用一空格隔开. 每 km 花费一个卢布.
输入输出样例
输入 #1 复制
- 7 9289 Vladivostok
- 5 8523 Chabarovsk
- 3 5184 Irkutsk
- 8 2213 Yalutorovsk
- 10 0 Moscow
输出 #1 复制 Yalutorovsk 112125
说明 / 提示
城市数量 <=150
距离 <=10000
同学个数 <=50
题解: 弱智小模拟~
- // luogu-judger-enable-o2
- // luogu-judger-enable-o2
- #include<cstdio>
- #include<iostream>
- #include<cmath>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- typedef long long ll;
- using namespace std;
- struct node{
- int x;
- int y;
- string s;
- }a[155];
- int n;
- ll ans1=2147483646666666;
- string ans2;
- int main(){
- while(1){
- n++; cin>>a[n].x>>a[n].y>>a[n].s;
- if(a[n].y==0) break;
- }
- for(int i=1;i<=n;i++){
- ll sum=0;
- for(int j=1;j<=n;j++)
- sum+=(ll)(a[j].x)*(ll)(abs(a[i].y-a[j].y));
- if(sum<=ans1){
- ans1=sum;
- ans2=a[i].s;
- }
- }
- cout<<ans2<<' '<<ans1;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3162488.html