前言(划重点)
1.题目要求n*(n-1)/2对,即不能重复
2.答案是 max(v[i],v[j]) × dis(i,j) 的求和解决方案
- 既然不能n方,那我们只好单独算出每头牛对于答案的贡献。所以可以按照v从小到大排序,这样可以直接通
过求出这头牛与之前的牛的总距离求出答案。 - 总距离
想一想我们怎么拆这个绝对值,因为我们只按照v的大小排序,没保证下标的有序。这时,我们试着拆一拆,假设有L头奶牛比当前i坐标小,R头比他的坐标大(R=i-1-L),用树状数组每次维护个数,以及坐标之和,求出小于当前下标的距离之和
- 既然不能n方,那我们只好单独算出每头牛对于答案的贡献。所以可以按照v从小到大排序,这样可以直接通
代码
//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops") //#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt") /* */ #include<bits/stdc++.h> #define R register #define ll long long #define inf INT_MAX using namespace std; const int N=5e4+10; int n; ll s[N],b[N]; //一个维护dis,一个维护个数 struct nkl { ll v,pos; }k[N]; inline ll god(nkl xx,nkl yy) { return xx.v<yy.v; } inline int lb(int x) { return x&(-x); } inline void add(int x) { int res=x; for (;x<=5e4;x+=lb(x)) b[x]++,s[x]+=res; } inline ll ask(int x) { ll res=0; for (;x;x-=lb(x)) res+=b[x]; return res; }//个数 inline ll find(int x) { ll res=0; for (;x;x-=lb(x)) res+=s[x]; return res; }//距离 int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%lld%lld",&k[i].v,&k[i].pos); sort(k+1,k+n+1,god); ll ans=0,sum=0; for (int i=1;i<=n;i++) { ll lk=ask(k[i].pos),rk=i-1-lk; //小的个数 ll le=find(k[i].pos),re=sum-le;sum+=k[i].pos; add(k[i].pos); ans+=k[i].v*(lk*k[i].pos-le+re-rk*k[i].pos); } printf("%lld\n",ans); return 0; }