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 且 \(a_i>a_j\)），将 \(len\) 选在 \([i,j]\) 这个区间，划分排序后，\(i\) 依然小于 \(j\)，所以 \(a_i\) 也依然会大于 \(a_j\)，故有解。