历届试题 小朋友排队

import java.util.Scanner;

class Friend{
    private int height;
    private int count;

    public Friend(int height) {
        super();
        this.height = height;
        this.count = 0;
    }

    public void setCount(int count) {
        this.count = count;
    }

    public int getHeight() {
        return height;
    }

    public int getCount() {
        return count;
    }
}

class Friends{
    private Friend[] friends;
    private Friend[] tmp;
    private long sum;

    public Friends() {
        super();
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        friends = new Friend[N];
        tmp = new Friend[N];
        sum = 0;
        for ( int i = 0 ; i < N ; i++){
            int height = in.nextInt();
            friends[i] = new Friend(height);
        }
        in.close();
    }

    public void Merge(int left,int right){
        int mid = (left + right) / 2;
        int i = left;
        int j = mid+1;
        int k = left;
        while((i<=mid) && (j<=right) ){
            if(friends[i].getHeight() <= friends[j].getHeight()){
                friends[i].setCount(friends[i].getCount()+j-mid-1);
                tmp[k++] = friends[i++];
            }else{
                friends[j].setCount(friends[j].getCount()+mid-i+1);
                tmp[k++] = friends[j++];
            }
        }

        while(j<=right){
            tmp[k++] = friends[j++];
        }
        j--;

        while(i<=mid){
            friends[i].setCount(friends[i].getCount()+j-mid);
            tmp[k++] = friends[i++];
        }

        for( i = 0 ; i <= right ; i++){
            friends[i] = tmp[i];
        }
    }

    public void MergeSort(int left,int right){
        if ( left == right ){
            return;
        }
        int mid = (left + right)/2;
        this.MergeSort(left, mid);
        this.MergeSort(mid+1, right);
        this.Merge(left, right);
    }

    public long All_Unhappy(){
        for ( int i = 0 ; i < this.friends.length ; i++){
            long s = friends[i].getCount();
            this.sum += (s+1)*s/2;
        }
        return this.sum;
    }

    public Friend[] getFriends() {
        return friends;
    }

}

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Friends test = new Friends();
        test.MergeSort(0, test.getFriends().length-1);
        System.out.print(test.All_Unhappy());
    }
}