这个题。。呃。。不说什么了，做过之后就是，没 有 心 得 ！！！
题意：给n个牛，并且给出它的坐标值x和声音值v，两只牛要说话。。然后两只牛说话时的音量为max{v[i],v[j]}*distance[i][j，然后求出所有牛说话时的总音量值
做法：
先对牛按照v从小到大排序。对于牛i，它与比他听力还小的牛之间交谈需要音量都是v[i]，再乘以之间的距离就可以了。
count[i]：比i听力小的且x坐标比第i头牛小的牛总数
total[i]：count[i]中那些牛的x坐标总和
∑(
v[i] * 所有比i听力小的牛到i的总距离 ）=∑( v[i] * (count[i]*x[i] – total + alltotal – total – (i – count[i] – 1) * x[i] ) )【这个公式ctrl c+v的。。实在打不出来。。。
count和total用树状数组啊。。。
因为要排序。。【排序还是java熟悉一点】
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
int []count=new int[20001];
int []total=new int[20001];
cow []cowarray=new cow[n+1];
int x,v;
for(int i=1;i<=n;i++)
{
v=scan.nextInt();
x=scan.nextInt();
cowarray[i]=new cow(x,v);
}
Arrays.sort(cowarray,1,n+1,new volumeCompare());
int now=0;
long c,t,sum=0;
for(int i=1;i<=n;i++)
{
now+=cowarray[i].getx();
update(1,cowarray[i].getx(),count);
update(cowarray[i].getx(),cowarray[i].getx(),total);
c=Sum(cowarray[i].getx(),count);
t=Sum(cowarray[i].getx(),total);
sum+=(long)(2*c*cowarray[i].getx()-2*t+now-i*cowarray[i].getx())*cowarray[i].getv();
}
System.out.println(sum);
}
static int lowbit(int x)
{
return x&(-x);
}
public static int Sum(int x,int[]c)
{
int result=0;
while(x>0)
{
result+=c[x];
x=x-lowbit(x);
}
return result;
}
public static void update(int a,int x,int[]c)
{
int n=c.length;
while(x<=n)
{
c[x]+=a;
x+=lowbit(x);
}
}
}
class cow
{
int x;
int v;
public cow(int x,int v)
{
this.x=x;
this.v=v;
}
public int getx()
{
return x;
}
public int getv()
{
return v;
}
}
class volumeCompare implements java.util.Comparator
{
public int compare(Object o1,Object o2)
{
cow cow1=(cow)o1;
cow cow2=(cow)o2;
return (int)(cow1.getv()-cow2.getv());
}
}