蓝桥杯小朋友排队JAVA

该问题的解法有两种

一：归并排序

归并排序的特点非常符合本题，本题要求只能相邻的元素相互交换，而归并排序本质排序也是这样；具体怎么解，看下边的代码，本人小白一个，参加了这次的java蓝桥杯，遇到这个题后，不知道如何解答，在网上搜到的大多是c/c++，搜到的java写的也大多有错误，写了好久总是不对，还以为本题无法用java写出，终于写出来了 哈哈  功夫不负有心人，注释中的数组都是值得对象数组，元素也是对象元素；

二：树状数组（不太了解这块，所以不说了）

import java.util.*;public class Main {

	/**
	 * @param args
	 */

public static class num //内部类
{
	public long h;//用long，否则会出错
	public long t;//用long,否则会出错
}
static num num1[]=new num[100001];//一开始开了100005个，但是造成了有一组测试数据超时
static num num2[]=new num[100001];//
	public static void main(String[] args) {

		for(int i=0;i<100001;i++)//对内部类对象初始化
		{
			num1[i]=new num();
			num2[i]=new num();
		}
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		for(int j=0;j		{
			num1[j].h=input.nextInt();
		}
		merge(num1,0,n-1);
		long sum=0;//必须用long，否则会错误
		for(int k=0;k		{
			//System.out.println(num1[k].h+" "+num1[k].t);
			sum+=(num1[k].t*(num1[k].t+1))/2;//等差数列求和公示 
		}
		
		System.out.println(sum);
}
	public static void merge(num a[],int left,int right)
	{
		if(left==right)   //终止递归的条件
		{
			return;
		}
		int mid=(left+right)/2;
		merge(a,left,mid);
		merge(a,mid+1,right);
		int p=left;
		int q=mid+1;
		int i=left;
	     while(p<=mid && q<=right)
	     {
	    	 if(a[p].h>a[q].h)
	    	 {
	    		 a[q].t+=mid+1-p;//如果左数组第一个元素比右数组第一个元素大，因为左右数组都是从小到大排序的
//所以左数组所有的元素（mid+1-p个）都大于右数组第一个元素;
 num2[i++]=a[q++];//注意这里交换的是类对象,这是归并排序的核心知识
	    	 }
	    	 else
	    	 {
	    		 a[p].t+=q-1-mid;//左数组的第一个元素小于或者等于右数组的第一个元素，q-1-mid==0,在右数组中，q所指的元素前面的元素就是小于p所指的元素，q-1-mid就是q所指元素的前边元素的个数;
	    		 num2[i++]=a[p++];
	    	 }
	     }
	     while(q<=right)//右数组有剩余，说明左数组的元素都比右数组剩下的元素小
	     {
	    	num2[i++]=a[q++];
	     }
	     q--;//在前边判断循环终止时q=last+1，所以循环终止，所以这里需要减去1
	     while(p<=mid)
	     {
	    	 a[p].t+=q-mid;
	    	num2[i++]=a[p++];
	     }
	     
	   
	    int j=left;
	     for(;j<=right;j++)
	     {
	    	 a[j]=num2[j];//将排序好的类对象数组传给原类对象数组
	     }
		
	}
}