POJ - 1990 MooFest

本文主要是介绍POJ - 1990 MooFest，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：一排牛，每头牛（坐标pos，听力v），如果牛i和牛j交流的话，需要max{v[i],v[j]}*abs(pos[i]-pos[j])，求两两交流的总和。

思路：还是求逆序数对的思想，按坐标排序后，求当前小于它听力的牛们的总花费，然后倒序后再求一遍就是结果了，

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int MAXN = 20005;
#define ll long long struct node{int pos,v;
}p[MAXN];
int n;
ll dis[MAXN],num[MAXN];bool cmp(node a,node b){return a.pos < b.pos;
}int lowbit(int x){return x&(-x);
}ll sum(int pos,ll x[]){ll ans = 0;while (pos > 0){ans += x[pos];pos -= lowbit(pos);}return ans;
}void add(int pos,int num,ll x[]){while (pos < MAXN){x[pos] += num;pos += lowbit(pos);}
}int main(){scanf("%d",&n);for (int i = 0; i < n; i++)scanf("%d%d",&p[i].v,&p[i].pos);sort(p,p+n,cmp);memset(dis, 0, sizeof(dis));memset(num, 0, sizeof(num));ll ans = 0;for (int i = 0; i < n; i++){ans += p[i].v * (p[i].pos*sum(p[i].v, num) - sum(p[i].v,dis));add(p[i].v, p[i].pos, dis);add(p[i].v, 1, num);}memset(dis,0,sizeof(dis));memset(num,0,sizeof(num));for (int i = n-1; i >= 0; i--){ans += p[i].v * (sum(p[i].v-1,dis) - p[i].pos*sum(p[i].v-1,num));add(p[i].v, p[i].pos, dis);add(p[i].v, 1, num);}cout<<ans<<endl;return 0;
}

这篇关于POJ - 1990 MooFest的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---