CF1815A Ian and Array Sorting 题解

题面。

直接进入主题吧。

思路

题目要求非递减序列，很明显，由题目给的操作，一定可以将这个序列的前 \(n - 1\) 项能够满足是非递减序列，最后只需要比较第 \(n\) 项是否大于等于第 \(n - 1\) 项即可。

解释一下为什么。对于序列 \(a\)，从 \(a_1\) 开始到 \(a_{n-1}\) 结束，每次对 \(a_i\) 与 \(a_{i+1}\) 进行操作使得 \(a_i\) 比 \(a_{i-1}\) 刚好大 \(1\) 或者相等，很明显这是可以做到的。由此可以将前 \(n-1\) 项变得符合题意的。

此时你会惊讶的发现这样连样例都过不了，仔细看会发现当 \(n\) 为奇数时程序就会输出 \(\texttt{No}\)。手推几个数据后，发现如果最后 \(a_{n-1}>a_n\)，可以将前 \(n-1\) 项全部减去一个极小值来达成非递减序列。说人话就是当 \(n\) 为奇数时直接输出 \(\texttt{YeS}\)。