首页 > 专题系列 > Java解POJ > POJ 2188 Cow Laundry [解题报告] Java
2013
11-10

POJ 2188 Cow Laundry [解题报告] Java

Cow Laundry

问题描述 :

The cows have erected clothes lines with N (1 <= N <= 1000) wires upon which they can dry their clothes after washing them. Having no opposable thumbs, they have thoroughly botched the job. Consider this clothes line arrangement with four wires:

Wire slot: 1 2 3 4
--------------- <-- the holder of the wires
\ \ / /
\ \/ /
\ /\ /
\ / \ / <-- actual clothes lines
/ \
/ \ / \
/ \/ \
/ /\ \
/ / \ \
--------------- <-- the holder of the wires
Wire slot: 1 2 3 4

The wires cross! This is, of course, unacceptable.

The cows want to unscramble the clothes lines with a minimum of hassle. Even their bovine minds can handle the notion of “swap these two lines”. Since the cows have short arms they are limited to swapping adjacent pairs of wire endpoints on either the top or bottom holder.

In the diagram above, it requires four such swaps in order to get a proper arrangement for the clothes line:


1 2 3 4
------------- <-- the holder of the wires
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
------------- <-- the holder of the wires
1 2 3 4

Help the cows unscramble their clothes lines. Find the smallest number of swaps that will get the clothes line into a proper arrangement.

You are supplied with clothes line descriptions that use integers to describe the current ordering of the clothesline. The lines are uniquely numbered 1..N according to no apparent scheme. You are given the order of the wires as they appear in the N connecting slots of the top wire holder and also the order of the wires as they appear on the bottom wire holder.

输入:

* Line 1: A single integer: N

* Lines 2..N+1: Each line contains two integers in the range 1..N. The first integer is the wire ID of the wire in the top wire holder; the second integer is the wire ID of the wire in the bottom holder. Line 2 describes the wires connected to top slot 1 and bottom slot 1, respectively; line 3 describes the wires connected to top and bottom slot 2, respectively; and so on.

输出:

* Line 1: A single integer specifying the minimum number of adjacent swaps required to straighten out the clothes lines.

样例输入:

4
4 1
2 3
1 4
3 2

样例输出:

4

解题代码:

//* @author: [email protected]
import java.io.*;
public class Main{
 static long ans=0;
 public static void main(String[] args) throws NumberFormatException, IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  int a=Integer.parseInt(in.readLine());
  ans=0;
  int[] arr=new int[a];
  int[] aww=new int[a];
  for(int i=0;i< a;i++)
  {
   String[] ss=in.readLine().split(" ");
   arr[i]=Integer.parseInt(ss[0]);
   aww[i]=Integer.parseInt(ss[1]);
  }
  for(int i=0;i< a;i++)
  {
   for(int j=0;j< a;j++)
    {
	if(arr[i]==aww[j])
	{
	  arr[i]=j;
	  break;
	}
     }
   }
  mergesort(arr,0,a);
  System.out.println(ans);
	
  }

  static void mergesort(int[] arr,int f,int n)
   {
   int n1,n2;
   if(n>1)
   {
    n1=n/2;
    n2=n-n1;
    mergesort(arr,f,n1);
    mergesort(arr,f+n1,n2);
    merge(arr,f,n1,n2);
    }
  }


  static void merge(int[] arr,int f,int n1,int n2)
   {
    int[] temp=new int[n1+n2];
    int cp=0,cp1=0,cp2=0,i=0;
    while((cp1< n1)&&(cp2< n2))
     {
	if(arr[f+cp1]< arr[f+n1+cp2])
	temp[cp++]=arr[f+(cp1++)];
	else {
		temp[cp++]=arr[f+n1+(cp2++)];
		ans+=n1-cp1;
	}
     }
     while(cp1< n1)
	temp[cp++]=arr[f+(cp1++)];
     while(cp2< n2)
	temp[cp++]=arr[f+n1+(cp2++)];
     for(i=0;i< cp;i++)
	arr[f+i]=temp[i];
   }
}

  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }