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#include #include using namespace std; struct node { double x; long long p; }D[15005]; bool cmp(node a,node b) { return (a.x =mid) break; } printf("%.5lfn",D[i].x); return 0; }
0 条评论。