首页 > 试题广场 >

而后单调

[编程题]而后单调

热度指数：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

说明

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

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

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

算法知识视频讲解

Gooby114514

发表于 2024-12-30 11:00:48

E 而后单调首先思考不可能的情况，分成两种：存在重复元素，那么最后就不可能是严格单调增或者严格单调减的情况，因此如果要满足题目要求，那么原数组必须要满足有至少长度为的区间能和最后排好的某一段是能匹配的，如果不能就是那么解法也很显然了，匹配的过程可以使用或者二分查找+双指针优化展开全文

FZANOTFOUND

发表于 2024-12-29 21:20:24

首先数组中的元素不能有重复的，否则不可能达到严格递增或严格递减。我们可以任意重排没有被选择的元素，所以被选中的个元素一定是严格递增或严格递减，且没有其他数据满足（即其余元素中没有元素在被选择的元素的最大值和最小值之间）我们可以对离散化处理，这样满足要求的元素一定是连续的() from bise 展开全文

Gnomeshgh112

发表于 2025-03-27 20:35:11

因为最后的结果要求是严格递增或者严格递减，所以如果原来的序列中存在相同的元素，直接判负考虑序列中不存在相同元素的情况，可以找到一个长度为m的单调递增或者单调递减的序列，查看其最大值和最小值在已经排序好的序列中的位置的差值是不是等于m。如果等于m，则说明未排序的序列中，其他n - m个数字，不会出现在展开全文

牛客856751393号

发表于 2025-03-10 15:06:22

def solve(num, m): n = len(num) dp = [0] * n # 表示以当前字符结尾的连续严格递增子数组的长度 dp[0] = 1 for i in range(1, n): if num[i] > num 展开全文

Leo米多

发表于 2025-05-19 18:31:19

#把sums元素和对应的位置index组成字典 #把sums排序，在排序后的sums取sum[i:i+m]个元素,判断这m个元素在原sums中的位置是不是连续的 def solve(sums): #把sums中的元素值和对应的位置index组成字典 dict_sums = {v:k 展开全文

why151

发表于 2025-03-18 15:59:59

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int t; cin>>t; whil 展开全文

蓝乐

发表于 2025-04-15 21:34:35

评论区的大佬个个都是人才，说话又好听 const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const re 展开全文

lhp_zml

发表于 2025-03-09 10:24:37

// 若存在，则在原数组与排好序的数组中必存在一段是相同的，段长>=m， // 可以用map或者二分快速定位到排好序的数组中，与原数组起点相同的位置，然后走一下这一段相同的有多长。 // 注意判断是否存在相同的数（严格单调），注意递增、递减排序都要判断一遍，递减不要用lower_bound # 展开全文

zy还能再战

发表于 2025-03-27 17:36:46

#牛客春招刷题训练营# + 链接想了半天最终决定还是暴力题目没有保证输入不重复，先判重，重了肯定不能单调然后遍历抽出哪一段，不在该段的全都插到平衡树里面，移动时只需要插一个数删一个数，单次复杂度O(logn)每次遍历在平衡树中查询（最小数）和（最大数+1）的序号，如果相等则说明当前这段可以插入到排序展开全文

已注销

发表于 2025-05-11 00:19:41

#include <iostream> #include <map> #include <vector> using namespace std; /* 最朴素的想法。如果而后单调，那么肯定满足一下条件： 1. 不包含重复元素。 2. 原始数组存在一个至少长展开全文

问题信息

哈希

难度：

7条回答 41收藏 357浏览

而后单调

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题