Johnny

用户名：JohnnyLin

访问量：1468

签　名：

等　　级
排　　名	25937
经　　验	539
参赛次数	0
文章发表	3
年　　龄	0
在职情况	学生
学　　校	广东金融学院
专　　业

　　自我简介：

TA的其他文章

蓝桥杯历届试题-小朋友排队树状数组AC代码（Java代码）
浏览：646

你可能喜欢

蓝桥杯历届试题-小朋友排队树状数组AC代码（Java代码）

　　作者: Johnny　　　　发表时间：2020-08-19 21:52:08 浏览：646　|　评论：1　

原题链接：蓝桥杯历届试题-小朋友排队

## 思路

小朋友从低到高排队 两两交换 则该小朋友需要交换的次数应该为： 左边比该小朋友身高高的个数加上 右边比该小朋友矮的个数 对统计得到的数求累加和即为该小朋友的不高兴程度

## 代码
```java
import java.util.Scanner;

/**
* @author JohnnyLin
* @version Creation Time：2020年8月17日 下午9:23:46
*/
public class Main {
	//h数组存放每个小朋友身高
	private static int h[];
	//树状数组c统计每个身高出现的次数
	public static int []c;
	//cnt数组存放每个小朋友的交换次数
	public static long []cnt;
	static int maxH=-1;
	
	//求二进制数第一个1所代表得十进制数值	
	/*如1100（十进制的12）的为100（十进制的4）
	求解过程如下
	 *		1100
	*&		1011
	*得	   1000
	 *则1100减1000得100为4	
	 */	
	private static int lowbit(int k) {
		return k-(k&(k-1));
	}
	//更新树状数组
	private static void update(int i,int n,int v,int []c) {
		for (int k = i; k<=n; k+=lowbit(k)) {
			c[k]+=v;
		}
	}
	//求树状数组前缀和
	private static long getSum(int i,int []c) {
		long ans=0;
		for (int k = i; k>=1 ; k-=lowbit(k)) {
			ans+=c[k];
		}
		return ans;
	}
	
	public static void main(String[] args) {
		Scanner reader=new Scanner(System.in);
		int n=reader.nextInt();
		h=new int[n];
		cnt=new long[n];
		for (int i = 0; i < n; i++) {
			h[i]=reader.nextInt();
			if(h[i]>maxH) maxH=h[i];
		}
		//身高作为动态数组c的下标 身高的最大值+1即为数组长度
		c=new int[maxH+2];
		//从左往右扫描一遍
		for (int i = 0; i < n; i++) {
			//动态维护树状数组
			update(h[i]+1,maxH+1,1,c);
			long sum=getSum(h[i]+1,c);//小于等于h[i]+1的数据的个数
			cnt[i]+=(i+1)-sum;	//总数减去小于等于h[i]+1的数据的个数得到 当前数据左侧比数据大的数的个数
		}
		//清零
		c=new int[maxH+2];
		//从右往左扫描一遍
		for (int i = n-1; i >= 0; i--) {
			//动态维护树状数组
			update(h[i]+1,maxH+1,1,c);
			cnt[i]+=getSum(h[i],c);//当前数据右侧比数据小的数据个数
		}
		long ans=0;
		for(int i=0;i<n;i++) {
			ans+=cnt[i]*(cnt[i]+1)/2;
		}
		System.out.println(ans);
//		for (int i = 1; i < c.length; i++) {
//			System.out.println(i+"----"+c[i]);
//		}
	}

}

```

0.0分

7 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

DB牛逼

2 63 8 29 1 7 3 9 30 2 35 65
怎么我用这个数据随便测一下,结果是2

2021-04-08 15:35:52

Johnny

TA的其他文章

你可能喜欢

C二级辅导-进制转换（C语言代码）

C二级辅导-公约公倍（C++代码）

C二级辅导-进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C++代码）

聪明的美食家（C语言代码）

蓝桥杯历届试题-小朋友排队树状数组AC代码（Java代码）

评论区

精彩推荐

【数组的距离】（C语言代码）

简单的a+b （C语言代码）

Pascal三角（C语言代码）格式错误

WU-输出九九乘法表（C++代码）

用筛法求之N内的素数。（C语言代码）

Tom数（C语言代码）

杨辉三角（C语言代码）

1054题解

排序算法（选择，插入，冒泡）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

Johnny

TA的其他文章

你可能喜欢

C二级辅导-进制转换 （C语言代码）

C二级辅导-公约公倍 （C++代码）

C二级辅导-进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C++代码）

聪明的美食家 （C语言代码）

蓝桥杯历届试题-小朋友排队 树状数组AC代码（Java代码）

评论区

精彩推荐

【数组的距离】 （C语言代码）

简单的a+b （C语言代码）

Pascal三角 （C语言代码）格式错误

WU-输出九九乘法表 （C++代码）

用筛法求之N内的素数。 （C语言代码）

Tom数 （C语言代码）

杨辉三角 （C语言代码）

1054题解

排序算法（选择，插入，冒泡）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C二级辅导-进制转换（C语言代码）

C二级辅导-公约公倍（C++代码）

C二级辅导-进制转换（C语言代码）

聪明的美食家（C语言代码）

蓝桥杯历届试题-小朋友排队树状数组AC代码（Java代码）

　　评论区

【数组的距离】（C语言代码）

Pascal三角（C语言代码）格式错误

WU-输出九九乘法表（C++代码）

用筛法求之N内的素数。（C语言代码）

Tom数（C语言代码）

杨辉三角（C语言代码）