Vijos 1036题:安装服务器
发布日期:2021-09-23 21:27:28 浏览次数:0 分类:技术文章

本文共 1306 字,大约阅读时间需要 4 分钟。

描述

政府计划建立一个大型的服务器中心,为各个城市提供网络服务。每个城市对网络的需求量是不一样的,而需求量越大,对线路的要求也就越高,线路的成本也就越高。因此需要选择合适的地点修建。每个城市用一个二维整数坐标表示,两个点之间的距离定义为水平距离+垂直距离,即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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Vijos 1072题:新年趣事之债务
下一篇:Vijos 1034题:家族

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.172.111.71]2022年05月22日 08时35分13秒