首页 > 试题广场 >

而后单调

[编程题]而后单调

热度指数：2552 时间限制：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}$ 问是否存在至少一种方案，使得最终得到的数组是个严格递增或严格递减数组。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入两个整数  代表数组长度、你需要取出的元素数量。
第二行输入  个整数  代表数组元素。

除此之外，保证单个测试文件的  之和不超过  。

输出描述:

对于每一组测试数据，如果存在至少一种方案，使得最终得到的数组是个严格递增或严格递减数组，在单独的一行上输出  ；否则，直接输出  。

示例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

说明

对于第一组测试数据，不需要进行任何操作，数组已经是严格递增数组。

对于第二组测试数据，选择区间  ，随后将这两个元素插入到  之前，得到  。

对于第三组测试数据，符合要求的方案为，选择区间  ，随后将剩余的元素重新排列得到  ，随后将这三个元素插入到  之后，得到  。

算法知识视频讲解

Python3

Chinry

T = int(input())

def ismonotone(num_list):
    if num_list[0] > num_list[-1]:
        return all(num_list[i - 1] > num_list[i] for i in range(1, len(num_list)))
    else:
        return all(num_list[i - 1] < num_list[i] for i in range(1, len(num_list)))
for i in range(T):
    n, m = list(map(int, input().split()))
    a = list(map(int, input().split()))
    output_str = "NO"
    if len(set(a)) != len(a):
        print("NO")
    elif n == m:
        print("YES" if ismonotone(a) else "NO")
    elif m == 1:
        print("YES")
    elif n-m==1:
        s_1,s_2=a[:-1],a[1:]
        if (ismonotone(a[:-1]) and (max(a)==a[-1]&nbs***bsp;min(a)==a[-1]))&nbs***bsp;(ismonotone(a[1:]) and (max(a)==a[0]&nbs***bsp;min(a)==a[0])):
            output_str = "YES"
        print(output_str)
    else:
        for i in range(n - m + 1):
            s = a[i: i + m]
            if ismonotone(s):
                t = sorted(a[:i] + a[i + m:]) if s[0]<s[-1] else sorted(a[:i] + a[i + m:],reverse=True)
                if max(s)<min(t)&nbs***bsp;min(s)>max(t):
                    output_str = "YES"
                else:
                    for j in range(1,len(t)):
                        if (t[j-1]>s[0] and t[j]<s[-1] and s[0]>s[-1])&nbs***bsp;(s[0]<s[-1] and t[j-1]<s[0] and t[j]>s[-1]):
                            output_str="YES"
                            break
                    if output_str=="YES":
                        break
        print(output_str)

写得有点点屎山，但跑得还挺顺畅

发表于 2026-01-01 15:33:35 回复(0)

Python3

牛客359589612号

t=int(input())

for _ in range(t):

n,m=map(int,input().split())

s=list(input().split())

s1=''.join(sorted(s))

s2=''.join(sorted(s,reverse=True))

s=''.join(s)

#print("s1",s1)

#print(s2)

if len(set(s))!=len(s):

print("NO")

else:

for i in range(n-m+1):

if s[i:i+m] in s1 or s[i:i+m] in s2:

print("YES")

break

#print(s[i:i+m])

else:

print("NO")

发表于 2025-07-04 14:36:06 回复(0)

提交观点

问题信息

哈希

难度：

2条回答 45收藏 482浏览

而后单调

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题