THU2017spring 1-4 Hospital 题解

THU2017spring 1-4 Hospital


描述

有n个村落分布在一条公路的沿线,为方便村民们就医,现打算在公路沿线修建一所医院。

由于各村落人数、年龄分布不同等原因,每个村落对医院的需求程度也不同。这里需求程度以一个非负的权值w表示:w越大,就医需求越大。对于一个选址方案,Σwi*di作为衡量其合理性的指标,其中wi和di分别表示第i个村落的权值和距离医院的距离,该指标越小,对应的选址就越优。请给出医院修建的最优位置。

输入

共n+1行。

第一行包含一个整数n;

以下共n行,每行包含两个整数:第一个为对应村落的一维坐标xi,第二个为对应村落的权值wi。

输出

共两行。

第一行为医院的最优坐标。

第二行为对应的最小权值,即医院选择最优坐标时的Σwi*di。

注意,如果有多个坐标权值均为最小值,请给出这些坐标中的最小者。

输入样例

1
2
3
4
3
3 5
7 11
5 6

输出样例

1
2
5
32

限制

1 <= n <= 300,000

村落的地址坐标是[0, 32767]的整数。

村落的权值是[1, 10^8]的整数。

时间:1 sec

空间:256 MB

提示

一级提示

● 可以在预处理时将坐标相同的村落合并。

二级提示

● 考虑医院选址向左(或向右)移动一个单位对Σwi*di的影响何时为正、何时为负。

● 注意你的程序是否能正确处理“有多个坐标权值均为最小值”的情况。

● 虽然最终选址坐标在int范围内,但计算Σwi*di的中间过程不一定在int范围内;可以使用long long,其表示的范围是[-2^63, 2^63)。

我也实在不知道该怎么做,参考twd2的做法什么“加权中位数”,胡作吧。最后80分。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int array[32768];
int abs(int x){
    if(x<0)return -x;
    return x;
}
int main(){
    ios::sync_with_stdio(false);
    memset(array,0,sizeof(array));
    int n;
    cin>>n;
    int total_wi=0;
    int max_xi=0;
    for(int i=0;i<n;i++){
        int xi,wi;
        cin>>xi>>wi;
        array[xi]+=wi;
        total_wi+=wi;
        if(max_xi<xi)max_xi=xi;
    }
    total_wi/=2;
    int wi=0;
    int pos;
    for(int i=0;i<=max_xi;i++){
        if(wi<total_wi&&total_wi<=wi+array[i]){
            pos=i;
            break;
        }else wi+=array[i];
    }
    long long sum=0;
    for(int i=0;i<=max_xi;i++){
        int t=array[i]*abs(pos-i);
        sum+=t;
    }
    cout<<pos<<endl<<sum;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注