寻找最佳聚会地点（0002）

题意

有一列火车，有不同的站点，每一个站点有一定数量的学生，我们把北京看作一个基准点，每一次输入一个站点的学生数量，距离北京的距离，该站点的名称，最后输入北京的学生数量，距离是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.最后按照要求输出答案即可?

希望能过程设

?

?

?