1215. 小朋友排队
摘要
Title: 1215. 小朋友排队
Tag: 树状数组
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1215. 小朋友排队
-
题意
n 个小朋友站成一排。
现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。
每个小朋友都有一个不高兴的程度。
开始的时候，所有小朋友的不高兴程度都是 0。
如果某个小朋友第一次被要求交换，则他的不高兴程度增加 1，如果第二次要求他交换，则他的不高兴程度增加 2（即不高兴程度为 3），依次类推。当要求某个小朋友第 k 次交换时，他的不高兴程度增加 k。
请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。
如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。 -
思路
求出每个小朋友的交换次数即可，即每个小朋友前面有多少比他大的，后面有多少比他小的
求出次数后，等差数列求和即可 -
代码
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
38
39
40
41
42
43
44
45
46
47
48
49'''
Author: NEFU AB-IN
Date: 2022-03-27 08:57:51
FilePath: \ACM\Acwing\1215.py
LastEditTime: 2022-03-27 08:57:52
'''
N = int(1e6 + 10)
tr, a, cnt = [0] * N, [0] * N, [0] * N
def lowbit(x):
return x & -x
def add(x, d):
while x < N:
tr[x] += d
x += lowbit(x)
def query(x):
res = 0
while x:
res += tr[x]
x -= lowbit(x)
return res
n = int(input())
a[1:] = list(map(int, input().split()))
for i in range(1, n + 1):
a[i] += 1
for i in range(1, n + 1):
add(a[i], 1)
cnt[i] += (i - query(a[i])) #当用到i-？时，先加进去再减，因为i代表的是目前树中有多少元素
tr = [0] * N
for i in range(n, 0, -1):
cnt[i] += query(a[i] - 1)
add(a[i], 1)
res = 0
for i in range(1, n + 1):
res += (cnt[i] * (cnt[i] + 1) // 2)
print(res)