C/C++教程

CF1637A Sorting Parts 题解

本文主要是介绍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\),故有解。

这篇关于CF1637A Sorting Parts 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!