蓝桥：重新排序（差分，python）

前言：

本题在模拟考试时还不会差分法，用纯暴力思路ac了60%的案列，之后看了蓝桥讲解，用差分做出来了（但对差分还是一知半解），最近学会了差分又来做本题，又卡在了技巧思路上，特写此篇博客来巩固一下，也希望能对大家有所帮助。对差分法还不了解的同学可以看此篇博客一维前缀和&一维差分（下篇讲解二维前缀和&二维差分）（超详细，python版，其他语言也很轻松能看懂）

问题描述:

给定一个数组 A 和一些查询 Li,Ri，求数组中第 Li 至第 Ri 个元素之和。
小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组，所有查询结果的总和最多可以增加多少?

输入格式
输入第一行包含一个整数 n。
第二行包含 n 个整数 A1,A2,⋅⋅⋅,An，相邻两个整数之间用一个空格分隔。
第三行包含一个整数 m 表示查询的数目。
接下来 m 行，每行包含两个整数 Li、Ri，相邻两个整数之间用一个空格分隔。

输出格式
输出一行包含一个整数表示答案。

数据范围
对于 30% 的评测用例，n,m≤50；
对于 50% 的评测用例，n,m≤500；
对于 70% 的评测用例，n,m≤5000；
对于所有评测用例，1≤n,m≤105，1≤Ai≤106，1≤Li≤Ri≤n。

输入样例：

5
1 2 3 4 5
2
1 3
2 5

输出样例：

4

样例解释
原来的和为 6+14=20，重新排列为 (1,4,5,2,3) 后和为 10+14=24，增加了 4。

思路：

用暴力思路来考虑此题的话只需要在草稿纸上把图画出来（数组尽量再取长一些），会发现需要改变的数字与它所被查询的次数相关。

以下标索引来说，如果该索引值被区间包含的次数越多（并集次数越多），则需要把数组中最大的数放在该索引上。例：在题目例子中，数组0,1,2,3,4,5中，所有查询结束后这些索引对应的次数应为[0,1,2,2,1,1]，所以要在两个2中放最大的数，1中放次大的数。

这样每次查询索引所被区间包含的次数为多少次时，每次查询改变索引下标出现的次数的时间复杂度为O(n)，查询次数一多就会超时。

这时就要考虑差分了，把每次查询的时间复杂度降为O(1)，但是本题差分如何差分呢？

定义差分数组时要理解本题的差分数组是干什么的！！！，本题差分数组是用来统计区间出现的次数， 所以定义为全0（未进行查询前，每个区间出现次数为0次），这点很重要！！！

本题还有一个问题点，求出差分后如何把数一一放在对应位置上呢？

这里有个小技巧，因为本题差分数组的定义是区间出现的次数，那么可以对原数组和差分数组进行排序，然后对应位置上所有原数组*差分数组的和就是总和，对于未排序前的数组统计和也可以用这个方法来降低时间复杂度

# 计算nums_1，原数组的和
nums_1 = 0
for i in range(1, n + 1):
    nums_1 += c[i] * a[i]  # 计算nums_1

# 对a和c进行排序
a.sort()  # 对数组a进行排序
c.sort()  # 对数组c进行排序

# 计算nums_2，排序后的最大和
nums_2 = 0
for i in range(1, n + 1):
    nums_2 += c[i] * a[i]  # 计算nums_2
1
2
3
4
5
6
7
8
9
10
11
12
13

代码及详细注释：

# 读取输入
n = int(input())  # 输入一个整数n
a = list(map(int, input().split()))  # 输入长度为n的整数列表a
m = int(input())  # 输入一个整数m

# 初始化数组a和b
a = [0, *a]  # 在a列表的开头插入一个0，使得a的下标从1开始
b = [0] * (n + 2)  # 初始化长度为n+2的全0列表b

# 处理区间操作
for i in range(m):
    l, r = map(int, input().split())  # 输入一个区间[l, r]
    b[l] += 1  # 区间左端点l对应的b值加1
    b[r + 1] -= 1  # 区间右端点r+1对应的b值减1

# 计算数组c
c = [0] * (n + 1)  # 初始化长度为n+1的全0列表c
for i in range(1, n + 1):
    c[i] = b[i] + c[i - 1]  # 计算c[i]，即前缀和

# 计算nums_1
nums_1 = 0
for i in range(1, n + 1):
    nums_1 += c[i] * a[i]  # 计算nums_1

# 对a和c进行排序
a.sort()  # 对数组a进行排序
c.sort()  # 对数组c进行排序

# 计算nums_2
nums_2 = 0
for i in range(1, n + 1):
    nums_2 += c[i] * a[i]  # 计算nums_2

# 输出结果
print(nums_2 - nums_1)  # 输出最终结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

总结：

本题是第十三届蓝桥杯省赛的题，掌握了差分做起来会发现很简单，用纯暴力做法思考起来也不是很难。