数学 + 带权中位数 - SGU 114 Telecasting station-白红宇

Telecasting station

Mean:

百慕大的每一座城市都坐落在一维直线上,这个国家的政府决定建造一个新的广播电视台。

经过了许多次试验后，百慕大的科学家们提出了一个结论:在每座城市的不满意度等于这座城市的市民数与这座城市与广播电视台的距离的乘积.

你需要找到这个一维直线上的一点来建造广播电视台，使得所有城市的不满意度的和最小.

analyse:

个人觉得应该是加权平均数，然而却是求中位数.

可以这样想：随便挑一个点作为station，左右移动一下看看移动之后能够减少多少不满同时又会增加多少不满就可以做了.

Time complexity: O(N)

view code

/**
 * -----------------------------------------------------------------
 * Copyright (c) 2016 crazyacking.All rights reserved.
 * -----------------------------------------------------------------
 *       Author: crazyacking
 *       Date  : 2016-01-07-09.46
 */
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using
namespace
std; 
typedef
long
long( 
LL); 
typedef
unsigned
long
long( 
ULL); 
const
double
eps( 
1e-8); 
const
int
MAXN
=
15010; 
struct N 
{ 
double
x; 
int p; 
}
a
[
MAXN
];
int b 
[
MAXN
];
int
cmp(N 
a
,N b) 
{ 
return
a
.
x
<b 
.
x; 
}
int
main() 
{ 
int n; 
while( 
scanf( 
"%d"
,
&n) 
!=
EOF) 
{ 
memset(b 
,
0
,
sizeof(b)); 
for( 
int
i
=
0; 
i
<n; 
i
++) 
scanf( 
"%d%d"
,
&
a
[
i
].
x
,
&
a
[
i
].p); 
sort( 
a
,
a
+n 
,
cmp); 
int s 
=
0; 
for( 
int
i
=
0; 
i
<n; 
i
++) 
{ 
            s 
+=
a
[
i
].p; 
            b 
[
i
]
=s; 
}
int
mid
=s 
/
2
,
w; 
for( 
int
i
=
0; 
i
<n; 
i
++) 
{ 
if(b 
[
i
]
>=
mid) 
{ 
w
=
i; 
break; 
}
}
printf( 
"%d
\n
"
,
a
[
w
].
x); 
}
return
0; 
}