粒子实验

时问限制：3000ms
内存限制：589824kb

题目描述：

​ 一些科学家在研究X粒子的特性，通常情况下，X粒子在经过加速装置后拥有的速度均为V,但是加热后,某些粒子的特性发生了变化，在相同情况下经过加速装置后拥有的速度变得大于V了（变化后的速度不一定相同），于是科学家们决定研究这些特别的粒子。

​ 科学家们对n个粒子做了特殊处理，为其从1到n分别编号，为了找出是哪些粒子的特性发生了变化（导致速度变化），他们准备让这些粒子依次通过一段相同长度的距离，速度越高的粒子通过这段距离所需的时间越短，由于技术问题，只能检测到粒子发射顺序和到达终点的顺序(没有两个粒子同时被发射或同时到达），请你通过这些数据计算出至少多少个例子特性发生了变化。（即速度大于通常情况）。

输入描述

第一行一个正整数n,表示粒子数星。
接下来一行包含n个正整数S1,S2.…Sn(1≤si≤n)，为按发射顺序给出的粒子编号，S1-Sn为1-n的一个排列。
接下来一行包含n个正整数P1,P2,… Pn(1≤pi≤n),为按到达终点顺序给出的粒子编号，p1-pn为1-n的一个排列。

轮出描述

输出至少有多少个粒子特性发生了变化(即速度大于通常情况)

输入样例

5

5 4 3 2 1

1 5 3 4 2

输出样例

2

输出解释： 发射顺序是5 4 3 2 1，到达顺序是1 5 3 4 2。

​ 可知1最晚发射，超过了前四个到达，1加速了。3在4之后发射的，但比4先到达了，所以3也加速了。

​ 输出2。

思路

​ 从上面的输出解释可以看出来1超过了前面4个，3超过了前面1个，其他的粒子没有超了0个。

​ 可以联想到，这道题用逆序数来解决。

逆序数

​ 在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。也就是说，对于n个不同的元素，先规定各元素之间有一个标准次序（例如n个 不同的自然数，可规定从小到大为标准次序），于是在这n个元素的任一排列中，当某两个元素的实际先后次序与标准次序不同时，就说有1个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。

​ 举个例子：

​ 5 4 2 3 1 —— 5的逆序数是4（比后面4个数都大），4的逆序数是3（比后面3个数大），2的逆序数是1，3的逆序数是1，1的逆序数是0

​ 5 1 3 2 4 —— 5的逆序数是4（比后面4个数都大），1的逆序数是0，3的逆序数是1，2的逆序数是0，4的逆序数是0

解题过程

以输入样例来举例：

5

5 4 3 2 1

1 5 3 4 2

​ 发射顺序：5 4 3 2 1

​ 到达顺序：1 5 3 4 2

​ 对应索引：4 0 2 1 3 【加上1后：5 1 3 2 4，实际含义是：粒子本应该是第x个到达的，但是如果他的逆序数大于0，则说明它超速了】

​ 逆序数： 4 0 1 0 0

​ 大于0的个数：2

以伪代码来描述：

​ 发射顺序：list_a

​ 到达顺序：list_b

​ 对应索引：list_c

​ 逆序数： list_d

​ ans： list_d中大于0的数

解题步骤：

1. 接收参数list_a和list_b，list_c和list_d初始化为0
2. 遍历list_b，找到每一个元素的对应索引，构成list_c
3. 算出list_c的逆序数，构成list_d
4. 计算list_d中大于0的数

代码

def getNum(num,lista):
    return lista.index(num)

n = int(input())
list_a = list(map(int,input().split()))
list_b = list(map(int,input().split()))
list_c = [0 for i in range(n)]
list_d = [0 for i in range(n)]

index_c=0
for i in list_b:
    list_c[index_c] = getNum(i,list_a)
    index_c+=1
    
for i in range(n):
    count = 0
    for j in list_c[i+1:]:
        if list_c[i] > j:
            count += 1
    list_d[i] = count
    
count = 0
for i in list_d:
    if i > 0:
        count += 1
print(count)

分析

时间复杂度O(N²)，空间复杂度O(N)

结果

AC率为73%