Codeforces 1349B - Orac and Medi

日常一道算法题。

翻译

有一个长度为 n 的整数数组 a。

每次操作可以选择一个子序列，让子序列的值变成中位数的值。

想要数组的值全都变成 k。

输入格式

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

每个测试用例输入两行，第一行输入整数 n k 用空格分隔，第二行输入 n 个整数。

可以保证 n 的和最大为 100000。(所以要用时间复杂度为 O(n) 的方式。)

输出格式

输出 yes 或 no

分析

超时超到崩溃，O(1) 写法各种超时，结果是因为，PyPy3 处理输入太慢了。

是一道脑筋急转弯的题目，如果字符串包含 k，长度为一或者串内包含大于 k 的连续值或者间隔值，就能递推出答案。

代码(Python 3)

# https://codeforces.com/problemset/problem/1349/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 run(n, k, s):
    i = 0
    have = False
    isSuccess = True if len(s) == 1 and s[0] == k else False
    while i < n:
        if s[i] == k:
            have = True
        if i < n - 1 and s[i] >= k and s[i + 1] >= k:
            isSuccess = True
        if i < n - 2 and s[i] >= k and s[i + 2] >= k:
            isSuccess = True
        i += 1

    return isSuccess and have

def case():
    arr = list(map(int, input().split(" ")))
    (n, k) = arr[0], arr[1]
    s = list(map(int, input().split(" ")))
    
    print("yes" if run(n, k, s) else "no")

for _ in range(t):
    case()

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

by 费城的二鹏 2020.06.04 长春