SGU114-Telecasting station-白红宇

SGU114-Telecasting station

阅读量：5118 次

发布时间：2019-06-13

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

114. Telecasting station

time limit per test: 0.5 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

41 32 15 26 2

Sample Output

3.00000

题意是说，有个国家的城市之间要建个公交（我英语不好、翻译可能会跑偏、也可能是电视塔、也可能是别的、我也不知道是啥），然后有一个不满意度，咱们自己想想也知道，肯定都喜欢把地铁站设在自己家门口。然后这个不满意度=城市的人数*这个站的位置。。。然后的然后、我也不会做这个题，直接上理论：数学家说，这是一个带权中位数问题，具体内容见 _ 这个讲的很明白了。然后，下面的代码就自然手到擒来了！！！

#include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  #include
                   
                    #include
                    
                     using namespace std;struct N{ double x; int p;} a[15009];int b[15009];int cmp(N a,N b){ return a.x
                     
                      =mid) { w=i; break; } } printf("%d\n",a[w].x); } return 0;}

转载于:https://www.cnblogs.com/riasky/p/3459254.html

你可能感兴趣的文章

第23月第24天 git命令 .git-credentials git rm --cached git stash clear