首页 > 其他分享 >CF1637A题解

CF1637A题解

时间:2024-01-17 19:24:09浏览次数:37  
标签:int 题解 len 数组 test array cases CF1637A

Sorting Parts

题面翻译

给定一个长度为 n 的数组 a。你可以执行恰好一次操作。每次操作选择一个在 [1,n-1] 内的整数 len,然后将数组 a 中长度为 len 的前缀和长度为 n-len 的后缀分别排序。请判断是否能够通过操作,使得最终的数组 a 满足 \forall i\in[1,n)a_i<= a(i+1)

数据范围:

  • t 组数据,1<= t<= 100
  • 2<= n,\sum n<= 10^4
  • 1<= a_i<= 10^9

Translated by Eason_AC

题目描述

You have an array a of length n . You can exactly once select an integer len between 1 and n - 1 inclusively, and then sort in non-decreasing order the prefix of the array of length len and the suffix of the array of length n - len independently.

For example, if the array is a = [3, 1, 4, 5, 2] , and you choose len = 2 , then after that the array will be equal to [1, 3, 2, 4, 5] .

Could it be that after performing this operation, the array will not be sorted in non-decreasing order?

输入格式

There are several test cases in the input data. The first line contains a single integer t ( 1 <= t <= 100 ) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains one integer n ( 2 <= n <= 10^4 ) — the length of the array.

The second line of the test case contains a sequence of integers a_1, a_2, ... , a_n ( 1 <= a_i <= 10^9 ) — the array elements.

It is guaranteed that the sum of n over all test cases does not exceed 10^4 .

输出格式

For each test case of input data, output "YES" (without quotes), if the array may be not sorted in non-decreasing order, output "NO" (without quotes) otherwise. You can output each letter in any case (uppercase or lowercase).

样例

样例输入

3
3
2 2 1
4
3 1 2 1
5
1 2 2 4 4

样例输出

YES
YES
NO

解题思路

由题可知这个操作就相当于把数组分为两半分别进行排序。通过样例不难看出,只要这一整个数组是非降序排列相当于升序,不过会有某些数相等的情况所以这么说,那么它分成两半再排序的结果与原来的数组是一样的。如果数组中有降序,就比如[1,3,2,4]其中的[3,2]就是降序,这时我们只要在[3,2]之间把数组分为两半进行排序它的结果就不是非降序排列的。

AC代码

#include<iostream>
#include<cstdio>
const int N = 1e4 + 10;
int q[N];
int main()
{
	int t, n;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		//要记住把falg的定义放在while循环里面。我就是忘了放,纠结了半天。qaq
		bool flag = 1;
		for (int i = 0; i < n; i++) {
			scanf("%d", &q[i]);
			if (q[i] < q[i - 1] && i > 0) {
				flag = 0;
			}
		}
		if (flag)
			printf("NO\n");
		else
			printf("YES\n");
	}
	return 0;
}

标签:int,题解,len,数组,test,array,cases,CF1637A
From: https://www.cnblogs.com/XiaoWang-554/p/17970842

相关文章

  • [ARC169E] Avoid Boring Matches 题解
    题目链接首先考虑无解的情况,一个显然的观察是如果R的个数大于一半,那么无论如何都会出现两个R比赛的情况,小于一半时我们可以调整使得B全都在前面,显然有解。接下来问题变为找到最优可行解,但是状态的合法性不是显然的,我们先尝试判定这个问题。先考虑第一轮比赛,显然我们想让......
  • SP839Optimal Marks 题解
    part1:建图二进制异或,每一位互不干扰。所以对每一位分开来考虑。然后变成了一个经典的模型。当前每一个未确定点有两个选择:变成\(1\),变成\(0\);已经确定的点只能选它本身的值。于是构造思路非常套路了:构造虚点\(S\)、\(T\)。对于一个点\(u\),从\(S\)连向\(u\)一条边,值为......
  • ABC311_g One More Grid Task 题解
    题目链接:Atcoder或者洛谷对于解决二维区间内的最值类型问题,我们常常有一类特别好用的方法,就是悬线法,它可以看做是单调栈的子集,但更加好理解和书写。对于悬线法,我们有一个常见的模型,找出面积最大的符合题意的最大的矩形:例题P4147玉蟾宫。对于悬线法而言,我们需要理解什么是悬......
  • P2216 [HAOI2007] 理想的正方形 题解
    题目链接:理想的正方形比较明显的,我们可以用二维ST表解决,具体的二维ST表的实现,只需要知道一点:对于\(st[i][j][t]=max(i\simi+2^t,j\simj+2^t)\),表示的是如图所示的大正方形范围内的最值,它可以拆成从四个小正方形的左端点走\(2^{t-1}\)长的小正方形组成,预处理完直接查......
  • 【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(上)
    知识盲点概念介绍HashMap是基于Map接口构建的数据结构,它以键值对的形式存储元素,允许键和值都为null。由于键的唯一性,HashMap中只能有一个键为null。HashMap的特点是元素的无序性和不重复性。注意,HashMap并不是线程安全的。在多线程环境下,如果不进行适当的同步处理,可能会导致数据不......
  • P9018 [USACO23JAN] Moo Route G 题解
    首先有一些性质。因为保证有解,所以\(a_i\)一定都是\(2\)的倍数(必须一来一回)。并且总的步数应该为\(\suma_i\)。先考虑\(n\le2\)的情况,这时我们可以分情况讨论。因为每一条线段都会被来回走两次,所以我们可以先把每一个数都除以\(2\)。若\(a=b\),则最优情况一定是形......
  • P9017 [USACO23JAN] Lights Off G 题解
    一次操作相当于把\(a\)异或上\(b\),修改开关的一位相当于将这一位异或上\(1\)。会发现一个很神奇的性质:初始开关对灯的影响和改变开关状态对灯的影响是独立的。而前者的影响是固定的,所以我们可以只考虑改变开关状态对灯的影响。假设一共需要\(k\)次操作能使所有灯关闭,如果我......
  • CF1876D Lexichromatography 题解
    Problem-D-CodeforcesLexichromatography-洛谷先注意读题:对于所有的值\(k\),在这个序列的任意子区间\([l,r]\)中,值为\(k\)且为红色的位置数减去值为\(k\)且为蓝色的位置数的绝对值不超过\(1\)注意是任意子区间这说明什么?说明如果只有第二个条件,我......
  • P2572 [SCOI2010] 序列操作 题解
    题解:序列操作比较综合的ds题,综合了线段树常见的几种操作:维护最大子段和、区间翻转、区间求和、区间覆盖。维护子段和常见的我们维护三类东西:前缀最长连续段、后缀最长连续段、当前区间上的最大子段和。在pushUp时,对于一个区间的前后缀最值首先等于左右子树的最长前后缀,......
  • P6054 题解
    blog。网络流——最小割。每个选手做某一套题的期望奖励固定,计算方式参考样例解释。这个假期望被去掉了。发现是典型的「\(m\)种强制选一」问题。考虑每个人都建一条链,跑最小割,每条链必定割\(\ge1\)条边,割哪条边就表示选哪套题。code,时间复杂度\(O(\text{能过})\)。......