51nod1110(xjb)

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1110

题意：中文题诶～

思路：可以将在 xi 位置，权值为 wi 的点看作有 wi 个点在 xi 位置．然后再按位置排一下序，再找中位数即可；

代码：

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #define ll long long
 5 using namespace std;
 6 
 7 const int MAXN = 1e4+10;
 8 pair<ll, ll> p[MAXN];
 9 
10 int main(void){
11     int n;
12     ll ans=0, sum=0;
13     scanf("%d", &n);
14     for(int i=0; i<n; i++){
15         scanf("%lld%lld", &p[i].first, &p[i].second);
16         ans+=p[i].second;
17     }
18     ans>>=1;
19     sort(p, p+n);
20     ll cnt=0;
21     int indx=-1;
22     while(1){
23         cnt += p[++indx].second;
24         if(cnt >= ans) break;
25     }
26     for(int i=0; i<n; i++){
27         if(i == indx) continue;
28         sum += abs(p[indx].first-p[i].first)*p[i].second;
29     }
30     printf("%lld
", sum);
31     return 0;
32 }

View Code