题目链接

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

题目大意

百慕大的每一座城市都坐落在一维直线上。这个国家的政府决定建造一个新的广播电视台。经过了许多次试验后,百慕大的科学家们提出了一个结论,在每座城市的不满意度等于这座城市的市民数与这座城市与广播电视台的距离的乘积。找到这个一维直线上的一点来建造广播电视台,使得所有城市的不满意度的和最小。

题解

易证,这个广播电视台必然会建在某个城市点上,否则必然不是最优解。

当每个城市都是1个人时,只有当电视台建在中间那个城市,所有人到电视台距离之和才为最小(奇数个城市时是中间的那个城市;偶数个城市时则为中间两个城市中的任意一个即可。)

但是,每个城市不止一人,该怎么处理呢?很容易,把每个城市的若干个人拆分成若干个小城市,只不过这些小城市都在同一个坐标而已。这样就可以解决了。

知识点

若最优点在T,则有:

∑{D[I]*DIST(I,T)}(I<>T)<=∑{D[I]*DIST(I,T+1)}(I<>T+1)

将此式化为:

∑{D[L]}*DIST(L,T)}+∑{D[R]*DIST(R,T)}+D[T+1]*DIST(T+1,T) <=∑{D[L]}*DIST(L,T+1)}+∑{D[R]*DIST(R,T+1)}+D[T]*DIST(T,T+1) (L<T&R>T+1) 

即:

∑{D[L]*DIST(L,T+1)}-∑{D[L]*DIST(L,T)}(L<T)+D[T]*(DIST(T,T+1))>=∑{D[R]*DIST(R,T)}-∑(D[R]*DIST(R,T+1))(R>T+1)+D[T+1]*(DIST(T,T+1))

进一步化简为:

∑{D[L]*(DIST(L,T)-DIST[L,T+1])}(L<=T)<=∑{D[R]*(DIST(R,T+1)-DIST(R,T))}(R>=T+1)

因为:

DIST(L,T)-DIST(L,T+1)=DIST(T,T+1)

DIST(R,T+1)-DIST(R,T)=DIST(T+1,T)

显然:

 DIST(T,T+1)=DIST(T+1,T)

因此:

∑D[L](L<=T)>=∑(D[R])(R>=T+1)

即:

∑D[L](L<T)+D[T]>=∑(D[R])(R>T)

我们发现,若T是最优点,则必有其左边的权值和加上D[T]后大于右边的权值和。而类似的,我们可以证明其右边的权值和加上D[T]后大于左边的权值和,因此我们要找的点也就是满足以上条件的点。注意到此时我们的选择已经和具体的位置(坐标)没有关系了,而成为主要考虑因素的仅仅是各点上的权值。 因为左边的权值和数+D[T]>=右边的权值和,那么: 

LEFTSUM+D[T]>=RIGHTSUM=SUMALL-(LEFTSUM+D[T]) =>2*(LEFTSUM+D[T])>=SUMALL =>2*RIGHTSUM<=SUMALL 

同理可得: 

RIGHTSUM+D[T]>=LEFTSUM=SUMALL-(RIGHTSUM+D[T]) =>2*(RIGHTSUM+D[T])>=SUMALL =>2*LEFTSUM<=SUMALL 

此时我们发现: 

2*LEFTSUM<=SUMALL 而 2*(LEFTSUM+D[T])>=SUMALL 

也即是说当前的位置T上的数包含了第[(SUMALL)/2]个数,这第[(SUMALL)/2]个数,就是这个序列中的带权中位数。所以这一类问题,实质上就是带权中位数问题。

代码

//
//  main.cpp
//  sgu
//
//  Site @haipz.com
//  Copyright (c) 2015年 林海鸿. All rights reserved.
//

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 150000;
struct node {
    double x;
    int p;
};
node a[N + 5];

bool cmp(node a, node b) {
    return a.x < b.x;
}

int main() {
    int n;
    scanf("%d", &n);
    double sum = 0.0;
    for (int i = 0; i < n; ++i) {
        scanf("%lf%d", &a[i].x, &a[i].p);
        sum += a[i].p;
    }
    sort(a, a + n, cmp);
    int t = 0;
    for (int i = 0; i < n; ++i) {
        t += a[i].p;
        if (t >= sum/2) {
            printf("%lf\n", a[i].x);
            break;
        }
    }
    return 0;
}
转载保留版权:http://haipz.com/blog/i/6449 - 海胖博客