蓝桥杯备考冲刺必刷题(Python) | 1264 排个序-文章教程-杰人编程网

学习Python从娃娃抓起！记录下蓝桥杯备考比赛学习过程中的题目，记录每一个瞬间。

附上汇总贴：蓝桥杯备考冲刺必刷题（Python） | 汇总-CSDN博客

【题目描述】

给定一个长度为n的数组a。给定一个长度为m的互不相同的数组p，意味着你可以交换a[pi] 和a[pi+1] 任意次。

请确定是否可以用仅允许的交换方式使得a数组非降序。

【输入】

第一行输入一个n和m。

第二行输入n个整数a1，a2，…，an。

第三行输入m个整数p1，p2，P3，…，Pm

1≤m≤n≤10^3，1≤ai≤n，1≦≤pi<n

【输出】

如果可以输出YES，否则输出NO。

【输入样例】

3 2
3 2 1
1 2

【输出样例】

YES

【代码详解】

n, m = [int(i) for i in input().split()]  # 输入n和m
a = [0 for i in range(n+1)]  # 初始化a数组
p = [0 for i in range(m+1)]  # 初始化p数组
b = [0 for i in range(n+1)]  # 初始化b数组
ls1 = [int(i) for i in input().split()]  # 输入a数组，下标从1开始
for i in range(1, n+1):
    a[i] = ls1[i-1]
ls2 = [int(i) for i in input().split()]  # 输入p数组，下标从1开始
for i in range(1, m+1):
    p[i] = ls2[i-1]
    b[ls2[i-1]] = 1  # 这里使用桶排序，用于后续判断下标是否合法
mark=0  # 定义标记位
for i in range(1, n):  # 冒泡排序模板
    for j in range(1, n-i):  # 从第1个到n-i个（这里不用加1是因为下面有j+1，会越界）
        if a[j]>a[j+1]:  # 如果前者大于后者（小于等于就不用交换）
            if b[j]==1:  # 如果下标在p数组中存在
                a[j], a[j+1] = a[j+1], a[j]  # 则进行交换
            else:  # 否则
                mark=1  # 修改标记位
                break  # 退出循环
    if mark==1:  # 退出循环
        break
if mark==0:  # 如果可以正常排序完，则肯定是非降序
    print("YES") 
else:  # 否则输出NO
    print("NO")

【运行结果】