Johnny

用户名：JohnnyLin

访问量：1544

签　名：

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

　　自我简介：

TA的其他文章

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

你可能喜欢

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

　　作者: Johnny　　　　发表时间：2020-08-19 21:52:08 浏览：678　|　评论：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编程助手吧

　　评论区

DB牛逼

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

2021-04-08 15:35:52

Johnny

TA的其他文章

你可能喜欢

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

【矩阵】（C语言代码）

蛇行矩阵（C语言代码）

点我有惊喜！你懂得！

点我有惊喜！你懂得！

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

评论区

精彩推荐

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

C语言考试练习题_排列（C++代码）

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

C语言训练-计算1977！* （C++代码）

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

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

蛇行矩阵（C语言代码）

【亲和数】（C语言代码）

有关字符，字符串的输入输出函数说明

字符串输入输出函数（C语言代码）

Johnny

TA的其他文章

你可能喜欢

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

【矩阵】 （C语言代码）

蛇行矩阵 （C语言代码）

点我有惊喜！你懂得！

点我有惊喜！你懂得！

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

评论区

精彩推荐

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

C语言考试练习题_排列 （C++代码）

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

C语言训练-计算1977！* （C++代码）

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

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

蛇行矩阵 （C语言代码）

【亲和数】 （C语言代码）

有关字符，字符串的输入输出函数说明

字符串输入输出函数 （C语言代码）

【矩阵】（C语言代码）

蛇行矩阵（C语言代码）

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

　　评论区

C语言考试练习题_排列（C++代码）

蛇行矩阵（C语言代码）

【亲和数】（C语言代码）

字符串输入输出函数（C语言代码）