2014蓝桥杯小朋友排队(归并排序和数状数组求逆序对)

你的名字 2022-03-06 07:24 167阅读 0赞

## 标题：小朋友排队 ##

n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，  
但是每次只能交换位置相邻的两个小朋友。  
每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。  
如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。  
请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。  
如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。

【数据格式】  
输入的第一行包含一个整数n，表示小朋友的个数。  
第二行包含 n 个整数 H1 H2 … Hn，分别表示每个小朋友的身高。  
输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。  
例如，输入：  
3  
3 2 1  
程序应该输出：  
9  
【样例说明】  
首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。

【数据规模与约定】  
对于10%的数据， 1<=n<=10；  
对于30%的数据， 1<=n<=1000；  
对于50%的数据， 1<=n<=10000；  
**对于100%的数据，1<=n<=100000，0<=Hi<=1000000。**

资源约定：  
峰值内存消耗 < 256M  
CPU消耗 < 1000ms

归并排序可以求总的逆序对，这个大家应该是知道的 。  
[他人 归并排序参考][Link 1]  
此题所求并非是总的逆序对， 而是相对的。

## 解题思想: ##

如果有如下序列：  
3 6 4 7 5 2 0 1  
那么对于1来说，要想回到前面， 必须要经过 2 5 7 4 6 3 次序并不重要， 重要的是个数。  
那么对于2来说，要被0 1经过。

那么总结一下就是：  
**就是相对于 2 来说有几个逆序对 即： 小于2并且在2右边的，大于2并且在其左边的， 取之和即为所求。**

接下来一张草图，来解释归并求逆序对的过程。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA5ODAx_size_16_color_FFFFFF_t_70]  
归并排序求逆序对代码如下:  
去掉含有 下面两个变量的代码所在行， 就是归并排序 **（ ni\_num\_sum，ni\_num\_sum\_temp ）**

#define MAX 1000005
    // 原数组 
    long num[MAX] = { 0};
    // 辅助排序 
    long num_sort[MAX] = { 0};
    
    // 去掉含有 下面两个变量的代码所在行， 就是归并排序
    // 记录左右两边的逆序 个数 
    long ni_num_sum[MAX] = { 0}; 
    // 辅助记录 
    long ni_num_sum_temp[MAX] = { 0};
    void pai_sort(int l, int mid, int r){ 
    	int i = l;
    	int j = mid + 1;
    	int index = l;
    	while(i <= mid && j <= r){ 
    		if(num[i] < num[j]){ 	// 后面大于前面 
    			num_sort[index] = num[i]; 
    			ni_num_sum[index] = ni_num_sum_temp[i] + (j - mid - 1); // 逆序数 
    			++i; 
    		}else if(num[i] > num[j]){  // 前面 大于 后面 出现逆序 
    			num_sort[index] = num[j]; 
    			ni_num_sum[index] = ni_num_sum_temp[j] + (mid - i + 1);	// 逆序数 
    			++j; 
    		} else{ // 等于， 不需要加逆序数 
    			num_sort[index] = num[i]; 
    			++i; 
    			num_sort[index] = num[j]; 
    			++j; 
    		}
    		++index;
    	}
    	while(i <= mid){ 
    		if(num[i] != num_sort[index])	// 如果出现相等的情况， 就不要计算
    			ni_num_sum[index] = ni_num_sum_temp[i] + (j - mid - 1);
    		num_sort[index] = num[i];
    		++index;
    		++i;
    	}
    	while(j <= r){  
    		if(num[i] != num_sort[index])	// 如果出现相等的情况， 就不要计算
    			ni_num_sum[index] = ni_num_sum_temp[j] + (mid - i + 1);
    		num_sort[index] = num[j];
    		++index;
    		++j;
    	}
    	// 排序完成 放回原数组， 并且将逆序结果缓存等待取用。
    	for(i = l; i <= r; ++i){ 
    		num[i] = num_sort[i];
    		ni_num_sum_temp[i] = ni_num_sum[i]; // 缓存上一次的逆序对数 
    	}
    }
    void gui_pai(int l, int r){ 
    	if(l < r){ 
    		int mid = (l + r) >> 1;
    		gui_pai(l, mid);
    		gui_pai(mid + 1, r);
    		pai_sort(l, mid, r);	
    	}
    }

**那么求出逆序对之后列 ？**

### 之后便是转换成不满意程度了。 ###

也好解决：  
比如 **2 有 7** 个逆序对，那么就是 1 + 2 + 3 + 4 + 5 + 6 + 7 也就是**n - 1求和**：  
对于 **n 到 1**的求和 求和公式为 \*\*( ( (n + 1) \* n) / 2 ) \*\* 。  
代码如下：

// 1 - n 连续数 求和 
    long sum_0_to_n(long n){ 
    	return ((n + 1) * n )>> 1;
    }

## 完整代码： ##

#include<stdio.h>
    #define MAX 1000005
    // 时间复杂度 O( N*log2(N) ) 
    long N = 0;
    
    // 原数组 
    long num[MAX] = { 0};
    // 辅助排序 
    long num_sort[MAX] = { 0};
    
    // 记录左右两边的逆序 个数 
    long ni_num_sum[MAX] = { 0}; 
    // 辅助记录 
    long ni_num_sum_temp[MAX] = { 0};
    
    unsigned long long ans = 0;
    // 1 - n 连续数 求和 
    long sum_0_to_n(long n){ 
    	return ((n + 1) * n )>> 1;
    } 
    void pai_sort(int l, int mid, int r){ 
    	int i = l;
    	int j = mid + 1;
    	int index = l;
    	while(i <= mid && j <= r){ 
    		if(num[i] < num[j]){ 	// 后面大于前面 
    			num_sort[index] = num[i]; 
    			
    			ni_num_sum[index] = ni_num_sum_temp[i] + (j - mid - 1); // 逆序数 
    			++i; 
    		}else if(num[i] > num[j]){  // 前面 大于 后面 出现逆序 
    			num_sort[index] = num[j]; 
    			ni_num_sum[index] = ni_num_sum_temp[j] + (mid - i + 1);	// 逆序数 
    			++j; 
    		} else{ // 等于， 不需要加逆序数 
    			num_sort[index] = num[i]; 
    			++i; 
    			num_sort[index] = num[j]; 
    			++j; 
    		}
    		index++;
    	}
    	while(i <= mid){ 
    		if(num[i] != num_sort[index]) 
    			ni_num_sum[index] = ni_num_sum_temp[i] + (j - mid - 1);
    		num_sort[index] = num[i];
    		++index;
    		++i;
    	}
    	while(j <= r){  
    		if(num[i] != num_sort[index])
    			ni_num_sum[index] = ni_num_sum_temp[j] + (mid - i + 1);
    		num_sort[index] = num[j];
    		++index;
    		++j;
    	}
    	// 放回 
    	for(i = l; i <= r; i++){ 
    		num[i] = num_sort[i];
    		ni_num_sum_temp[i] = ni_num_sum[i]; // 缓存上一次的逆序对数 
    	}
    }
    void gui_pai(int l, int r){ 
    	if(l < r){ 
    		int mid = (l + r) >> 1;
    		gui_pai(l, mid);
    		gui_pai(mid + 1, r);
    		pai_sort(l, mid, r);	
    	}
    } 
    int main(){ 
    	scanf("%d", &N);
    	for(int i = 0; i < N; i++){ 
    		scanf("%d", num + i);
    	} 
    	gui_pai(0, N - 1);
    	// 使用逆序对 计算结果
    	for(int i = 0; i < N; ++i){ 
    		ans += sum_0_to_n(ni_num_sum[i]);
    	} 
    	printf("%lld\n", ans);
    	for(int i = 0; i < N; i++){ 
    		printf("%d ", ni_num_sum[i]);
    	}
    	return 0;	
    }

## 解题思想二 数状数组： ##

同样是求逆序对， 但是求解方式不同。  
同样一张草图， 表示解题过程。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA5ODAx_size_16_color_FFFFFF_t_70 1]

#include<stdio.h>
    #define N_MAX 100005
    // 时间复杂度 O( N*log2(N) ) 
    
    long N = 0;
    // 原数组 
    long num[N_MAX] = { 0};
    // 这里需要使用数字的最大值存放数据, 因为这相等于背包 
    #define MAX 1000005 
    // 树状数组解法
    // 需要两个数组 
    long tree_num_left[MAX];
    long tree_num_right[MAX];
    // 存放求和结果 
    long ans_num_left[MAX];
    long ans_num_right[MAX];
    // 存放最大方便确定扫描区间 减少复杂度 
    long max_num = -999999;
    inline int low_bit(int t){ 
    	return t&(-t);
    } 
    // 求和 
    inline long tree_sum(long tree_num[], long index){ 
    	long sum = 0;
    	for(long i= index; i > 0; i -=low_bit(i)){ 
    		sum +=  tree_num[i];
    	}
    	return sum;
    } 
    // 更新单节点
    inline void update(long tree_num[], int index, long num){ 
    	for(int i = index; i <= max_num; i += low_bit(i)){ 
    		tree_num[i] += num;
    	}
    }
    int main(){ 
    	
    	scanf("%d", &N);
    	for(int i = 0; i < N; i++){ 
    		scanf("%d", num + i);
    		if(num[i] > max_num){ 
    			max_num = num[i];
    		} 
    	} 
    	max_num ++; // 因为会出现0的情况， 将最大值加1就可以， 相当于向右偏移1， 当然 多加也无所谓 
    	
    	// 树状数组解法 
    	
    	// 更新 由左向右扫描 
    	for(int i = 0; i < N; ++i){ 
    		update(tree_num_left, num[i] + 1, 1); 
    		// 若是 替换成 ans_num_right[num[i]] 数据将变得有序 ， 但是后续合并和计算复杂度 最差 将会变高10倍 
    		// 而且并不需要有序， 只需要结果就好 
    		ans_num_left[i] = tree_sum(tree_num_left, max_num) - tree_sum(tree_num_left, num[i] + 1); 
    	}
    	// 更新 由右向左扫描 
    	for(int i = N - 1; i >= 0; --i){ 
    		update(tree_num_right, num[i] + 1, 1); 
    		ans_num_right[i] = tree_sum(tree_num_right, num[i]); 
    	}
    	// 合并 
    	unsigned long long ans_2 = 0;
    	for(int i = 0; i < N; ++i){ 
    		ans_num_right[i] += ans_num_left[i]; 
    		// 求值
    		ans_2 += sum_0_to_n(ans_num_right[i]);
    		printf("%ld ", ans_num_right[i]);
    	} 
    	puts("");
    	printf("树状数组求得：%lld\n", ans_2);
    	
    	return 0;	
    }

运行截图：

## 归并排序 和 数状数组全部代码 ##

#include<stdio.h>
    #define N_MAX 100005
    // 时间复杂度 O( N*log2(N) ) 
    
    long N = 0;
    // 原数组 
    long num[N_MAX] = { 0};
    // 辅助排序 
    long num_sort[N_MAX] = { 0};
    
    // 记录左右两边的逆序 个数 
    long ni_num_sum[N_MAX] = { 0}; 
    // 辅助记录 
    long ni_num_sum_temp[N_MAX] = { 0};
    
    
    
    unsigned long long ans = 0;
    
    // 1 - n 连续数 求和 
    long sum_0_to_n(long n){ 
    	return ((n + 1) * n )>> 1;
    } 
    
    void pai_sort(int l, int mid, int r){ 
    	int i = l;
    	int j = mid + 1;
    	int index = l;
    
    	while(i <= mid && j <= r){ 
    		if(num[i] < num[j]){ 	// 后面大于前面 
    			num_sort[index] = num[i]; 
    			
    			ni_num_sum[index] = ni_num_sum_temp[i] + (j - mid - 1); // 逆序数 
    			++i; 
    		}else if(num[i] > num[j]){  // 前面 大于 后面 出现逆序 
    			num_sort[index] = num[j]; 
    			
    			ni_num_sum[index] = ni_num_sum_temp[j] + (mid - i + 1);	// 逆序数 
    			++j; 
    		} else{ // 等于， 不需要加逆序数 
    			num_sort[index] = num[i]; 
    			++i; 
    			num_sort[index] = num[j]; 
    			++j; 
    		}
    		index++;
    	}
    	while(i <= mid){ 
    		
    		if(num[i] != num_sort[index]) 
    			ni_num_sum[index] = ni_num_sum_temp[i] + (j - mid - 1);
    		num_sort[index] = num[i];
    		++index;
    		++i;
    	}
    	while(j <= r){  
    		if(num[i] != num_sort[index])
    			ni_num_sum[index] = ni_num_sum_temp[j] + (mid - i + 1);
    		num_sort[index] = num[j];
    		++index;
    		++j;
    	}
    	// 放回 
    	for(i = l; i <= r; i++){ 
    		num[i] = num_sort[i];
    		ni_num_sum_temp[i] = ni_num_sum[i]; // 缓存上一次的逆序对数 
    	}
     
    }
    void gui_pai(int l, int r){ 
    	
    	if(l < r){ 
    		int mid = (l + r) >> 1;
    		gui_pai(l, mid);
    		gui_pai(mid + 1, r);
    		
    		pai_sort(l, mid, r);	
    	}
    	
    } 
    
    
    // 这里需要使用数字的最大值存放数据, 因为这相等于背包 
    #define MAX 1000005 
    // 树状数组解法
    // 需要两个数组 
    long tree_num_left[MAX];
    long tree_num_right[MAX];
    // 存放求和结果 
    long ans_num_left[MAX];
    long ans_num_right[MAX];
    // 存放最大方便确定扫描区间 减少复杂度 
    long max_num = -999999;
    inline int low_bit(int t){ 
    	return t&(-t);
    } 
    // 求和 
    inline long tree_sum(long tree_num[], long index){ 
    	long sum = 0;
    	for(long i= index; i > 0; i -=low_bit(i)){ 
    		sum +=  tree_num[i];
    	}
    	return sum;
    } 
    // 更新单节点
    inline void update(long tree_num[], int index, long num){ 
    	for(int i = index; i <= max_num; i += low_bit(i)){ 
    		tree_num[i] += num;
    	}
    }
    
    int main(){ 
    	
    	scanf("%d", &N);
    	for(int i = 0; i < N; i++){ 
    		scanf("%d", num + i);
    		if(num[i] > max_num){ 
    			max_num = num[i];
    		} 
    	} 
    	max_num ++; // 因为会出现0的情况， 将最大值加1就可以， 相当于向右偏移1， 当然 多加也无所谓 
    	
    	// 树状数组解法 
    	
    	// 更新 由左向右扫描 
    	for(int i = 0; i < N; ++i){ 
    		update(tree_num_left, num[i] + 1, 1); 
    		// 若是 替换成 ans_num_right[num[i]] 数据将变得有序 ， 但是后续合并和计算复杂度 最差 将会变高10倍 
    		// 而且并不需要有序， 只需要结果就好 
    		ans_num_left[i] = tree_sum(tree_num_left, max_num) - tree_sum(tree_num_left, num[i] + 1); 
    	}
    	// 更新 由右向左扫描 
    	for(int i = N - 1; i >= 0; --i){ 
    		update(tree_num_right, num[i] + 1, 1); 
    		ans_num_right[i] = tree_sum(tree_num_right, num[i]); 
    	}
    	// 合并 
    	unsigned long long ans_2 = 0;
    	for(int i = 0; i < N; ++i){ 
    		ans_num_right[i] += ans_num_left[i]; 
    		// 求值
    		ans_2 += sum_0_to_n(ans_num_right[i]);
    		printf("%ld ", ans_num_right[i]);
    	} 
    	puts("");
    	printf("树状数组求得：%lld\n", ans_2);
    	 
    	
    	gui_pai(0, N - 1);
    	// 使用逆序对 计算结果
    	for(int i = 0; i < N; ++i){ 
    		ans += sum_0_to_n(ni_num_sum[i]);
    	} 
    	for(int i = 0; i < N; ++i){ 
    		printf("%ld ", ni_num_sum[i]);
    	} 
    	puts("");
    	printf("归并排序求得: %lld\n", ans);
    	
    	
    	
    		
    	
    	return 0;	
    }

运行截图:  
![在这里插入图片描述][20190318121715317.png]

[Link 1]: https://www.cnblogs.com/skywang12345/p/3602369.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA5ODAx_size_16_color_FFFFFF_t_70]: /images/20220306/e29d7195c1824bf9bc64226afcf6f165.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA5ODAx_size_16_color_FFFFFF_t_70 1]: /images/20220306/5d5b656df0de4f04a9c9b2651cf0c153.png
[20190318121715317.png]: /images/20220306/40e7a58a202948dfbf5d1599c7f40927.png