Codeforces 1365B - Trouble Sort

日常一道算法题。

翻译

麻烦的排序

有 n 个元素排列在一行

元素用两个数字表示 a[i] 表示元素的值 和 b[i] 可能是 0 或 1。他想排列这些元素以 a[i] 升序。

它可以进行任意次数的以下操作：

• 选择两个元素 i 和 j，并且保证 b[i] != b[j]，交换他们。

告诉他，能否排序成 a 的升序。

输入格式

输入整数 t 表示测试用例组数。

每个测试用例输入三行，第一行输入 n，第二行输入数组 a，第三行输入数字 b

输出格式

每个测试用例输出 Yes 或 No。

分析

原本想复杂了，写了冒泡排序和选择排序，结果第二个测试用例都没过。

最后想了想，发现只要 b 里面 0 和 1 都有，就能任意交换，所以就能排序成功。或者原本就是有序的，就能成功。

代码(Python3)

# https://codeforces.com/problemset/problem/1365/B
 
import sys
import os
import heapq
import math
 
try:
    path = "./file/input.txt"
    if os.path.exists(path):
        sys.stdin = open(path, 'r')
    # sys.stdout = open(r"./file/output.txt", 'w')
except:
    pass
 
t = int(input())
 
def printd(value):
    # print(value)
    pass
 
def case():
    n = int(input())
    a = list(map(int, input().split(" ")))
    b = list(map(int, input().split(" ")))

    one = False
    zero = False
    
    answer = True
    for i in range(0, n):
        if i < n - 1:
            if a[i + 1] < a[i]:
                answer = False
        if b[i] == 0:
            one = True
        else:
            zero = True

    print("Yes" if answer or (one and zero) else "No")

for _ in range(t):
    case()

更多代码尽在 https://github.com/Tconan99/Codeforces

by 费城的二鹏 2020.06.14 长春