寻找最佳聚会地点(0002)

发布时间:2023年12月20日

题意

有一列火车,有不同的站点,每一个站点有一定数量的学生,我们把北京看作一个基准点,每一次输入一个站点的学生数量,距离北京的距离,该站点的名称,最后输入北京的学生数量,距离是0,北京的名字,输入结束,一个学生乘坐一公里火车花费一元钱,问:选择哪一个站点可以使得所有学生的花费总和最小(只计算单程),如果有相同的答案,输出离北京最近的站点

输入

7 9289 上海

5 8523 西安

3 5184 重庆

8 2213 广州

10 0 北京

输出

广州 112125

数据范围

城市数量不大于150,每一个站点距离北京的距离不大于10000,每一个站点的学生数目不大于50

代码

#include<bits/stdc++.h>

using namespace std;

struct Place
{
	int num;
	int len;
	string name;
}place[200];

int cmp(Place a,Place b)
{
	return a.len<b.len;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int a,b,cnt=0;
	string s;
	while(cin>>a>>b>>s)
	{
		place[cnt].num=a;
		place[cnt].len=b;
		place[cnt].name=s;
		cnt++;
		if(b==0)	break;
	}
	
	sort(place,place+cnt,cmp);
	
	int min_money=150*1e4*50+10;
	string ans;
	for(int i=0;i<cnt;i++)
	{
		int sum=0;
		for(int j=0;j<cnt;j++)
		{
			sum+=abs(place[j].len-place[i].len)*place[j].num;	
		}
		if(sum<min_money)
		{
			min_money=sum;
			ans=place[i].name;
		}
	}
	
	cout<<ans<<" "<<min_money<<endl;
	
	return 0;
}

总结

1.结构体

因为我们要存同一个站点的学生数目,站点距离北京的距离,站点的名字,所以最好使用一个结构体来保存

结构体的定义格式是这样的

struct Place
{
	int num;
	int len;
	string name;
}place[200];

2.重载小于号

因为我们要对结构体进行排序,而且需要按照距离来进行排序,所以我们就使用这个格式来重载小于号

int cmp(Place a,Place b)
{
	return a.len<b.len;
}

3.排序

排序的时候,加上我们自定义的排序要求

sort(place,place+cnt,cmp);

4.暴力枚举每一种情况

从北京站开始枚举,计算站点之间的距离使用减法,因为可能出现负数的情况,比如说北京站到任何一站都是负数(负数不符合现实意义),所以加上绝对值函数,计算总费用并且维护一个最小的总费用

因为我们从北京站开始计算的,所以最后算出的答案一定是离北京站最近的站点(假设有两个站点的费用相同),因为更新的条件是严格小于才会更新

5.最后按照要求输出答案即可?

希望能过程设

?

?

?

文章来源:https://blog.csdn.net/L3102250566/article/details/135117626
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。