基准时间限制:1 秒 空间限制:131072 KB
X轴上有N个点,每个点除了包括一个位置数据X[i],还包括一个权值W[i]。该点到其他点的带权距离 = 实际距离 * 权值。求X轴上一点使它到这N个点的带权距离之和最小,输出这个最小的带权距离之和。
Input
第1行:点的数量N。(2 <= N <= 10000)
第2 - N + 1行:每行2个数,中间用空格分隔,分别是点的位置及权值。(-10^5 <= X[i] <= 10^5,1 <= W[i] <= 10^5)
Output
输出最小的带权距离之和。
Input示例
5
-1 1
-3 1
0 1
7 1
9 1
Output示例
20
思路:中位数。
将点的权值看成多个点就行。然后求中位数。
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<math.h>
5 using namespace std;
6 typedef struct node
7 {
8 int x;
9 int cost ;
10 } ss;
11 ss id[20000];
12 bool cmp(node p,node q)
13 {
14 return p.x<q.x;
15 }
16 typedef long long LL;
17 int main(void)
18 {
19 int n,i,j;
20 scanf("%d",&n);
21 LL sum = 0;
22 for(i = 0; i < n; i++)
23 {
24 scanf("%d %d",&id[i].x,&id[i].cost);
25 sum += id[i].cost;
26 }
27 LL mid = (sum+1)/2;
28 sort(id,id+n,cmp);
29 LL ak = 0;
30 for(i = 0; i < n; i++)
31 {
32 ak+=id[i].cost;
33 if(ak >= mid)
34 {
35 break;
36 }
37 }
38 int x =id[i].x;sum = 0;
39 for(i = 0;i < n;i ++)
40 {
41 sum += (LL)abs(id[i].x-x)*id[i].cost;
42 }
43 printf("%lld\n",sum);
44 return 0;
45 }