【SGU】 114. Telecasting station 中位数

本文主要是介绍【SGU】 114. Telecasting station 中位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：【SGU】 114. Telecasting station

题目分析：一个位置多个城市可以看成多个城市在同一位置，然后就可以求中位数了，易知最优的位置一定在中位数上。

代码如下 ：

#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std ;typedef long long LL ;#define rep( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )
#define mid ( ( l + r ) >> 1 )const int MAXN = 15005 ;struct Node {int a , b ;bool operator < ( const Node& t ) const {return a < t.a ;}
} ;Node p[MAXN] ;
int n ;void solve () {int tot = 0 ;For ( i , 1 , n ) {scanf ( "%d%d" , &p[i].a , &p[i].b ) ;tot += p[i].b ;}sort ( p + 1 , p + n + 1 ) ;tot = ( tot + 1 ) / 2 ;For ( i , 1 , n ) {if ( tot - p[i].b <= 0 ) {printf ( "%.10f\n" , ( double ) p[i].a ) ;return ;}tot -= p[i].b ;}
}int main () {while ( ~scanf ( "%d" , &n ) ) solve () ;return 0 ;
}

这篇关于【SGU】 114. Telecasting station 中位数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---