本文共 1176 字，大约阅读时间需要 3 分钟。

描述

政府计划建立一个大型的服务器中心，为各个城市提供网络服务。每个城市对网络的需求量是不一样的，而需求量越大，对线路的要求也就越高，线路的成本也就越高。因此需要选择合适的地点修建。每个城市用一个二维整数坐标表示，两个点之间的距离定义为水平距离＋垂直距离，即a,b两点间距离为D(a,b)=|Xa-Xb|+|Ya-Yb|。对于每个城市，线路的费用为：费用＝距离×人口×城市的网络需求程度。总的费用为各个城市的费用的总和。请你找出最适合安装服务器（既总费用最小）的整数坐标（不一定要在城市上）。

格式

输入格式

输入第一行有一个正整数N（N ≤ 100000），表示城市的数量。后面的n行每行描述一个城市，每行有四个整数x，y，p，k分别表示城市的坐标，人口数，以及网络需求程度。（0 < x, y < 2^31；p≤600, k ≤30）

输出格式

输出包含一行。在这一行中，应当包含两个整数x，y表示最优解的坐标，如果有多个最优解，那么输出x最小的，如果有x相同，那么输出y最小的。

样例1

样例输入1

52 3 5 32 1 100 302 2 1 13 2 7 61 1 4 30

样例输出1

2 1

#include 
   
    #include 
    
     using namespace std;struct node{
   	long x;	long y;	long z;}a[100000];int cmpx(node a, node b) {
    return a.x < b.x; }int cmpy(node a, node b) {
    return a.y < b.y; }int main(){
   	int n, i;	long k, p, all = 0, tmp;	scanf("%d", &n);	for (i = 0; i < n; i++)	{
   		scanf("%ld%ld%ld%ld", &a[i].x, &a[i].y, &k, &p);		all += k*p;		a[i].z = k*p;	}	sort(a, a + n, cmpx);	for (i = 0, tmp = 0; i < n; i++)	{
   		tmp += a[i].z;		if (tmp >= all / 2) {
    printf("%ld ", a[i].x); break; }	}	sort(a, a + n, cmpy);	for (i = 0, tmp = 0; i < n; i++)	{
   		tmp += a[i].z;		if (tmp >= all / 2) {
    printf("%ld\n", a[i].y); break; }	}	return 0;}
    
   

转载地址：https://blog.csdn.net/bodhiye/article/details/70846607 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！