CF1637A Sorting Parts 题解

题目传送门

题意简述

给你一个长度为 \(n\) 的数组 \(a\),你可以选择 \(1\sim n-1\) 的一个数 \(len\),分别对 \([1,len]\) 和 \([len+1,n]\) 排序,如果存在一个 \(len\) 能使数组非升序输出 YES,否则输出 NO

分析

这题我的考场代码被 hack 了,暴力枚举会 TLE。

我们分类讨论数组 \(a\):

1. \(a\) 有序

当 \(a\) 有序时,无论选择哪个 \(len\),都不可能使数组无序,所以无解。

2. \(a\) 无序

当 \(a\) 无序时,存在逆序对(\(i<j\) 且 \(a_i>a_j\)),将 \(len\) 选在 \([i,j]\) 这个区间,划分排序后,\(i\) 依然小于 \(j\),所以 \(a_i\) 也依然会大于 \(a_j\),故有解。

上一篇:【模拟】AcWing 155. 内存分配


下一篇:C语言程序设计100例之(67):大整数加法