首页 > 代码库 > 51nod1110(xjb)
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\n", sum); 31 return 0; 32 }
51nod1110(xjb)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。