首页 > 试题广场 >

而后单调

[编程题]而后单调
  • 热度指数：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\} 。
算法知识视频讲解
添加回答
Python 3
菜鸟小乔头像 菜鸟小乔
T = int(input())

def is_sorted(A: list):
    if A == sorted(A):
        return 1
    elif A == sorted(A, key=lambda x: -x):
        return -1
    return 0

def check(A: list, m: int):
    for i in range(n - m+1):
        j = i + m
        M = A[i:j]
        # M 必须是严格单调的
        result_M = is_sorted(M)
        if not result_M:
            continue

        if result_M == 1:  # 升序
            left = sorted(A[:i] + A[j:])
            if left[0] > M[-1] or left[-1] < M[0]:
                return True
            for k in range(len(left) - 1):
                if left[k] < M[0] and M[-1] < left[k + 1]:
                    return True

        elif result_M == -1:  # 降序
            left = sorted(A[:i] + A[j:], key=lambda x: -x)
            if M[-1] > left[0] or M[0] < left[-1]:
                return True
            for k in range(len(left) - 1):
                if left[k] > M[0] and M[-1] > left[k + 1]:
                    return True
    return False

for _ in range(T):
    n, m = map(int, input().split())
    A = [int(i) for i in input().split()]
    # print(n,m)
    if is_sorted(A):
        print("YES")
        continue
    if len(set(A)) < n:
        print("NO")
        continue
    if check(A, m):
        print("YES")
    else:
        print("NO")

发表于 2025-07-28 16:20:58 回复(0)
提交观点

问题信息

哈希
难度：
3条回答 358浏览

热门推荐

相关试题

而后单调

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号