首页 > 试题广场 >

而后单调

[编程题]而后单调

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

输入描述:

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

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

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

输出描述:

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

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

说明

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

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

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

算法知识视频讲解

Java

Sen🍓🍀

Java卡输入超时4/20, 使用 BufferedReader

发表于 2025-10-09 14:33:12 回复(0)

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)

请叫我牛柳

import bisect

def is_single_up(seq: list):
    if len(seq) == 1:
        return True
    delt = [i - j for i, j in zip(seq[1:], seq[:-1])]
    if min(delt) > 0:
        return True
    return False

def is_single_down(seq: list):
    delt = [i - j for i, j in zip(seq[:-1], seq[1:])]
    if min(delt) > 0:
        return True
    return False

def is_single(seq: list):
    return is_single_up(seq)&nbs***bsp;is_single_down(seq)

def try_seq_son_in_seq_rest(seq_son: list, seq_rest: list, reverse=False):
    # 统一处理成单调递增
    if reverse:
        seq_son = sorted(seq_son)
    a, b = seq_son[0], seq_son[-1]
    
    seq_rest = sorted(seq_rest)
    
    if a > seq_rest[-1]&nbs***bsp;b < seq_rest[0]:
        return True
    else:
        if len(seq_rest) == 1:
            return False

        if (bisect.bisect_left(seq_rest, b) - (bisect.bisect_right(seq_rest, a) - 1)) == 1:
            return True

    return False

for _ in range(int(input())):
    n, m = input().split(' ')
    n, m = int(n), int(m)

    seq = list(map(int, input().split(' ')))

    result = 'NO'
    if n > 1e3:
        pass
    elif is_single(seq):
        result = 'YES'
    else:
        for i in range(n - m + 1):
            seq_son = seq[i:i+m]
            seq_rest = seq[:i] + seq[i+m:]

            if is_single(seq_son):
                if try_seq_son_in_seq_rest(seq_son, seq_rest, reverse=(seq_son[-1] - seq_son[0]) <= 0):
                    result = 'YES'
                    break
            else:
                continue
    print(result)

发表于 2025-07-04 23:06:24 回复(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)

emdnauoy

t = int(input())

def is_conti(ls):

if all(ls[i]>ls[i+1] for i in range(len(ls)-1)) or all(ls[i]<ls[i+1] for i in range(len(ls)-1)):

return True

else:

return False

while True:

try:

ls1 = list(map(int,input().split()))

ls2 = list(map(int,input().split()))

n = ls1[0]

m = ls1[1]

min2 = min(ls2)

max2 = max(ls2)

ex = False

if n == m:

ex = True

else:

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

in_ls = ls2[i:i+m]

if (min2 in in_ls or max2 in in_ls) and n!=m+1:

ex = False

else:

res = is_conti(in_ls)

if res:

ex = True

break

if ex:

print('YES')

else:

print('NO')

except:

break

发表于 2025-04-20 11:15:29 回复(0)

pypy3

一个毕业生a

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)

大话家

就是过不了，也是服了，你们看看？怎么优化。

import java.util.*;
import java.util.stream.Collectors;

public class Main {

    private static final String YES = "YES";
    private static final String NO = "NO";

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Integer num = Integer.parseInt(in.nextLine());
        String[] result = new String[num];

        for (int i = 0; i < num; i++) {
            Integer m = Integer.parseInt(in.nextLine().split(" ")[1]);
            String[] data = in.nextLine().split(" ");
            List<Integer> list = Arrays.stream(data).map(Integer::parseInt).collect(
                                     Collectors.toList());
            result[i] = fun1(list, m);
        }

        for (int i = 0; i < num; i++) {
            System.out.println(result[i]);
        }
    }

    public static String fun1(List<Integer> list, int len) {
        List<Integer> sortList = new ArrayList<>(list);
        Collections.sort(sortList);
        int listSize = list.size();
        for (int i = 0; i <= listSize - len; i++) {
            List<Integer> ele = list.subList(i, i + len);
            String str = fun2(sortList, ele);
            if (YES.equals(str)) {
                return YES;
            }
        }
        return NO;
    }

    public static String fun2(List<Integer> resource, List<Integer> target) {
        int n = resource.size(), m = target.size();

        for (int i = 0; i <= n - m; i++) {
            boolean forwardMatch = true, backwardMatch = true;

            for (int j = 0; j < m; j++) {
                if (!resource.get(i + j).equals(target.get(j))) {
                    forwardMatch = false;
                }
                if (!resource.get(n - 1 - i - j).equals(target.get(j))) {
                    backwardMatch = false;
                }
                if (!forwardMatch && !backwardMatch) {
                    break;
                }
            }

            if (forwardMatch || backwardMatch) {
                return YES;
            }
        }

        return NO;
    }

}

发表于 2025-03-04 20:34:04 回复(0)

提交观点

问题信息

哈希

难度：

7条回答 41收藏 361浏览

而后单调

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题