SGU 114 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=114

114. Telecasting station

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

Every city in Berland is situated on Ox axis. The government of the country decided to build new telecasting station. After many experiments Berland scientists came to a conclusion that in any city citizens displeasure is equal to product of citizens amount in it by distance between city and TV-station. Find such point on Ox axis for station so that sum of displeasures of all cities is minimal.

Input

Input begins from line with integer positive number N (0<N<15000) – amount of cities in Berland. Following N pairs (X, P) describes cities (0<X, P<50000), where X is a coordinate of city and P is an amount of citizens. All numbers separated by whitespace(s).

Output

Write the best position for TV-station with accuracy 10-5.

Sample Input

4
1 3
2 1
5 2
6 2

Sample Output

3.00000

带权中位数的题目,利用带权中位数的性质就可以解出来.

题目中的人口就是权值.按位置排序后,设要求的地点为 xk ,那 xk 必须满足|xk-x0|*w0 + |xk-x1|*w1 + ... + |xk-xn-1)|*wn-1 的值最小,令W = sigma(wi),则带权中位数xk满足:

sigma(wi)(xi < xk) <= W/2
sigma(wi)(xi > xk) <= W/2

CODE

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
 
struct node
{
  double x;
  long long p;
}D[15005];
 
bool cmp(node a,node b)
{
  return (a.x<b.x);
}
 
int main()
{
  int n,i;
  scanf("%d",&n);
  for(i=0;i<n;i++){
      scanf("%lf%lld",&D[i].x,&D[i].p);
  }
  sort(D,D+n,cmp);
  for(i=1;i<n;i++){
      D[i].p+=D[i-1].p;
  }
  long long mid=D[n-1].p/2;
  for(i=0;i<n;i++){
      if(D[i].p>=mid) break;
  }
  printf("%.5lfn",D[i].x);
  return 0;
}
» 本博客采用署名 2.5 中国大陆许可协议进行许可,本文版权归作者所有,欢迎转载,但必须在明显位置给出原文连接。
anyShare分享到:
发表评论?

0 条评论。

发表评论

注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>