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

POJ 1804 Brainman [解题报告] Java

Brainman

问题描述 :

Background

Raymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant just by glancing at them. And he can even count Poker cards. Charlie would love to be able to do cool things like that, too. He wants to beat his brother in a similar task.

Problem

Here’s what Charlie thinks of. Imagine you get a sequence of N numbers. The goal is to move the numbers around so that at the end the sequence is ordered. The only operation allowed is to swap two adjacent numbers. Let us try an example:

Start with: 2 8 0 3

swap (2 8) 8 2 0 3

swap (2 0) 8 0 2 3

swap (2 3) 8 0 3 2

swap (8 0) 0 8 3 2

swap (8 3) 0 3 8 2

swap (8 2) 0 3 2 8

swap (3 2) 0 2 3 8

swap (3 8) 0 2 8 3

swap (8 3) 0 2 3 8


So the sequence (2 8 0 3) can be sorted with nine swaps of adjacent numbers. However, it is even possible to sort it with three such swaps:

Start with: 2 8 0 3

swap (8 0) 2 0 8 3

swap (2 0) 0 2 8 3

swap (8 3) 0 2 3 8


The question is: What is the minimum number of swaps of adjacent numbers to sort a given sequence?Since Charlie does not have Raymond’s mental capabilities, he decides to cheat. Here is where you come into play. He asks you to write a computer program for him that answers the question. Rest assured he will pay a very good prize for it.

输入:

The first line contains the number of scenarios.

For every scenario, you are given a line containing first the length N (1 <= N <= 1000) of the sequence,followed by the N elements of the sequence (each element is an integer in [-1000000, 1000000]). All numbers in this line are separated by single blanks.

输出:

Start the output for every scenario with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the minimal number of swaps of adjacent numbers that are necessary to sort the given sequence. Terminate the output for the scenario with a blank line.

样例输入:

4
4 2 8 0 3
10 0 1 2 3 4 5 6 7 8 9
6 -42 23 6 28 -100 65537
5 0 0 0 0 0

样例输出:

Scenario #1:
3

Scenario #2:
0

Scenario #3:
5

Scenario #4:
0

解题代码:

//* @author 
import java.util.*;
public class Main {   
    
   static int count=0;
    /**  
     * @param args  
     */  
    public static void main(String[] args) {  
       Scanner in=new Scanner(System.in);
       String  t=in.nextLine();
       int tcase=Integer.parseInt(t);
  
       for(int j=1;j<=tcase;j++){
         count=0;
         String str = in.nextLine();
         String b[]=str.split("\\s");
        
         int n=Integer.parseInt(b[0]);
         int a[]=new int[n];
         for(int i=0;i< n;i++)
           a[i]=Integer.parseInt(b[i+1]);
      
         sort(a);
         System.out.println("Scenario #"+j+":"); 
         System.out.println(count);
         System.out.println();
        }
	 
    }   
       
       
    public static void sort(int arr[]) {
          
        int temp[] = new int[arr.length];   
        mergeSort(arr,temp,0,arr.length-1);
       
    }   
       
    private static void mergeSort(int arr[],int temp[],int m,int n) {   
        if (m == n) return;   
        int mid = (m+n)/2;   
        mergeSort(arr, temp, m, mid);   
        mergeSort(arr, temp, mid+1, n);   
        for (int i = m; i <= n; i++) {   
            temp[i] = arr[i];   
        }   
        int index1 = m;   
        int index2 = mid + 1;   
        int index = m;   
  
        while (index1 <= mid && index2 <= n) {   
            if (temp[index1] <= temp[index2]) {   
                arr[index++] = temp[index1++];   
            } else {   
                arr[index++] = temp[index2++];   
                count=count+mid-index1+1;
            }   
        }   
        while(index1 <= mid) {   
            arr[index++] = temp[index1++];   
        }   
        while(index2 <= n) {   
            arr[index++] = temp[index2++];   
        }   
           
    }   
  
}

  1. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  2. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  3. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

  4. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  5. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  6. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。