首页 > 专题系列 > Java解POJ > POJ 1990 MooFest [解题报告] Java
2013
11-10

POJ 1990 MooFest [解题报告] Java

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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
/*
 *参考大牛的程序,第一次写树状树组...
 *先将cows以volume为关键字排序..
 *两个树状数组,一个维护点个数,一个维护前面坐小于当前点的坐标之和
 */
class cin
{
 static BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
 static StringTokenizer st;
 static int leave=0;
 static int nextInt() throws IOException
 {
  while(leave==0)
  {
   st=new StringTokenizer(in.readLine());
   leave=st.countTokens();
  }
  leave--;
  return Integer.parseInt(st.nextToken());
 }
 static boolean hasNext() throws IOException
 {
  while(leave==0)
  {
   String temp=in.readLine();
   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;