首页 > 试题广场 >

而后单调

[编程题]而后单调
  • 热度指数:2300 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
\hspace{15pt}对于给定的由 n 个整数组成的数组 \left\{a_1, a_2, \dots, a_n\right\} ,你需要按照下述规则进行操作:

{\hspace{20pt}}_\texttt{1.}\,从数组中选出连续的 m 个元素(即选择一个长度为 m 的连续子数组);

{\hspace{20pt}}_\texttt{2.}\,将数组中剩余的 n - m 个元素重新排序;

{\hspace{20pt}}_\texttt{3.}\,在重新排序后的数组中选择一个位置,顺序插入刚刚选出的 m 个元素;

\hspace{15pt}问是否存在至少一种方案,使得最终得到的数组是个严格递增或严格递减数组。

输入描述:
\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 2 \times 10^5\right) 代表数据组数,每组测试数据描述如下:

\hspace{15pt}第一行输入两个整数 n,m\left(1\leqq n \leqq 2 \times 10^5;\ 1\leqq m \leqq n\right) 代表数组长度、你需要取出的元素数量。
\hspace{15pt}第二行输入 n 个整数 a_1, a_2, \dots, a_n\left(1\leqq a_i\leqq 10^9\right) 代表数组元素。

\hspace{15pt}除此之外,保证单个测试文件的 n 之和不超过 2 \times 10^5


输出描述:
\hspace{15pt}对于每一组测试数据,如果存在至少一种方案,使得最终得到的数组是个严格递增或严格递减数组,在单独的一行上输出 \textrm{YES} ;否则,直接输出 \textrm{NO}
示例1

输入

4
5 5
1 2 3 4 5
3 2
9 2 4
6 3
12 3 8 7 6 5
5 3
1 3 2 4 5

输出

YES
YES
YES
NO

说明

\hspace{15pt}对于第一组测试数据,不需要进行任何操作,数组已经是严格递增数组。

\hspace{15pt}对于第二组测试数据,选择区间 [2,3] ,随后将这两个元素插入到 9 之前,得到 \{{\color{orange}2}, {\color{orange}4}, 9\}

\hspace{15pt}对于第三组测试数据,符合要求的方案为,选择区间 [3,5] ,随后将剩余的元素重新排列得到 \{12, 5, 3\} ,随后将这三个元素插入到 12 之后,得到 \{12, {\color{orange}8}, {\color{orange}7}, {\color{orange}6}, 5, 3\}
def is_up_or_down(s):
    up = sorted(s)
    down = sorted(s,reverse=True)
    if up == s:
        return 1#up
    elif down == s:
        return 2#down
    else:
        return False
#s1 is up


def is_have_up(s1,s2):
    s2.sort()
    for i in range(len(s2)+1):
        if i == 0:
            if s1[-1] < s2[i]:
                return True
        elif i == len(s2):
            if s1[0] > s2[i-1]:
                return True
        else:
            if s2[i-1] < s1[0] and s1[-1] <s2[i]:
                return True
    return False

def is_have_down(s1,s2):
    s2.sort(reverse = True)
    for i in range(len(s2)+1):
        if i == 0:
            if s1[-1] > s2[i]:
                return True
        elif i == len(s2):
            if s1[0] < s2[i-1]:
                return True
        else:
            if s2[i-1] > s1[0] and s1[-1] > s2[i]:
                return True
    return False

def have_solution(s,m):
    if len(s) == m:
        if is_up_or_down(s):
            return 'YES'
        else:
            return 'NO'
    i = 0
    while i + m <= len(s):
        s_tichu = s[i:i + m]
        s_shenxia = s[:i] + s[i + m:]
        if is_up_or_down(s_tichu):
            if is_up_or_down(s_tichu) == 1:
                if is_have_up(s_tichu, s_shenxia):
                    return 'YES'
            elif is_up_or_down(s_tichu) == 2:
                if is_have_down(s_tichu, s_shenxia):
                    return 'YES'
        i += 1
    return 'NO'

n = int(input())
for k in range(n):
    a,b = map(int,input().split())
    shuzhu = list(map(int,input().split()))
    print(have_solution(shuzhu,b))
#有超时,力竭

发表于 2025-04-11 02:26:38 回复(0)