THU2017spring 1-4 Hospital
描述
有n个村落分布在一条公路的沿线，为方便村民们就医，现打算在公路沿线修建一所医院。
由于各村落人数、年龄分布不同等原因，每个村落对医院的需求程度也不同。这里需求程度以一个非负的权值w表示：w越大，就医需求越大。对于一个选址方案，Σwi*di作为衡量其合理性的指标，其中wi和di分别表示第i个村落的权值和距离医院的距离，该指标越小，对应的选址就越优。请给出医院修建的最优位置。
输入
共n+1行。
第一行包含一个整数n；
以下共n行，每行包含两个整数：第一个为对应村落的一维坐标xi，第二个为对应村落的权值wi。
输出
共两行。
第一行为医院的最优坐标。
第二行为对应的最小权值，即医院选择最优坐标时的Σwi*di。
注意，如果有多个坐标权值均为最小值，请给出这些坐标中的最小者。
输入样例
3
3 5
7 11
5 6
输出样例
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; } |