2013
11-10

# MooFest

Every year, Farmer John’s N (1 <= N <= 20,000) cows attend "MooFest",a social gathering of cows from around the world. MooFest involves a variety of events including haybale stacking, fence jumping, pin the tail on the farmer, and of course, mooing. When the cows all stand in line for a particular event, they moo so loudly that the roar is practically deafening. After participating in this event year after year, some of the cows have in fact lost a bit of their hearing.

Each cow i has an associated “hearing” threshold v(i) (in the range 1..20,000). If a cow moos to cow i, she must use a volume of at least v(i) times the distance between the two cows in order to be heard by cow i. If two cows i and j wish to converse, they must speak at a volume level equal to the distance between them times max(v(i),v(j)).

Suppose each of the N cows is standing in a straight line (each cow at some unique x coordinate in the range 1..20,000), and every pair of cows is carrying on a conversation using the smallest possible volume.

Compute the sum of all the volumes produced by all N(N-1)/2 pairs of mooing cows.

* Line 1: A single integer, N

* Lines 2..N+1: Two integers: the volume threshold and x coordinate for a cow. Line 2 represents the first cow; line 3 represents the second cow; and so on. No two cows will stand at the same location.

* Line 1: A single line with a single integer that is the sum of all the volumes of the conversing cows.

4
3 1
2 5
2 6
4 3


57


//* @author:
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
/*
*参考大牛的程序,第一次写树状树组...
*先将cows以volume为关键字排序..
*两个树状数组,一个维护点个数,一个维护前面坐小于当前点的坐标之和
*/
class cin
{
static StringTokenizer st;
static int leave=0;
static int nextInt() throws IOException
{
while(leave==0)
{
leave=st.countTokens();
}
leave--;
return Integer.parseInt(st.nextToken());
}
static boolean hasNext() throws IOException
{
while(leave==0)
{
if(temp==null)return false;
st=new StringTokenizer(temp);
leave=st.countTokens();
}
return true;
}
}

class TreeArray
{
int value[],n;
TreeArray(int num)
{
n=num;
value=new int[n+1];
Arrays.fill(value,0);
}

int lowBit(int t)
{
return t&(t^(t-1));
}

void plus(int a,int i)
{
while(i<=n)
{
value[i]+=a;
i+=lowBit(i);
}
}

int getSum(int i)
{
int sum=0;
while(i>0)
{
sum+=value[i];
i=i-lowBit(i);
}
return sum;
}
}

class Moo
{
int x,v;
Moo(int a,int b)
{
v=a;x=b;
}
}

class Cmp implements Comparator< Object>
{
public int compare(Object a,Object b)
{
if(((Moo)a).v>((Moo)b).v)return 1;
return -1;
}
}

class MooFest
{
TreeArray count,total;
long sum=0,now=0;
int n,i;
Moo cow[];
MooFest() throws IOException
{
n=cin.nextInt();
cow=new Moo[n+1];
count=new TreeArray(20000);
total=new TreeArray(20000);
for(i=1;i<=n;i++)
{
cow[i]=new Moo(cin.nextInt(),cin.nextInt());
}
Arrays.sort(cow,1,n+1,new Cmp());
}

long totalV()
{
int c,t;
for(i=1;i<=n;i++)
{
now+=cow[i].x;
count.plus(1,cow[i].x);
total.plus(cow[i].x,cow[i].x);
c=count.getSum(cow[i].x);
t=total.getSum(cow[i].x);
sum+=(long)(2*c*cow[i].x-2*t+now-i*cow[i].x)*cow[i].v;
}
return sum;
}
}
public class Main {
public static void main(String args[]) throws IOException
{
MooFest data=new MooFest();
System.out.println(data.totalV());
}
}

1. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。

2. 我没看懂题目
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
第二个是7 0 6 -1 1 -6 7输出是14 7 7
不知道题目例子是怎么得出来的

3. int half(int *array,int len,int key)
{
int l=0,r=len;
while(l<r)
{
int m=(l+r)>>1;
if(key>array )l=m+1;
else if(key<array )r=m;
else return m;
}
return -1;
}
这种就能避免一些Bug
l,m,r
左边是l,m;右边就是m+1,r;