hiho一下第276周《数组重排2》题目分析

0
0

本题是一道比较简单的贪心题目。

我们假设从A1, A2, ... AN从挑选了K个数,把他们放到最左边之后可以使得序列是递增排列的。

那么被挑选的这K个数一定是在新数列的前K个,而未被挑选的N-K个数一定是按照原顺序留在新数列的最后N-K个。

又因为新数列是递增的,所以未被挑选的N-K个数在原序列中一定是K+1, K+2, K+3, ... N。并且是按顺序排列的。

我们现在要K最小,也就找到最小的K,满足K+1, K+2, ... N在原序列中是按从左到右排列的。

于是直接贪心找出K即可。

1 answer(s)

0

找到最长特殊递增序列,这个递增序列满足: 该序列恰好是原序列排序后的后缀。 这个时候,剩余的元素就是需要移动的元素。 所以答案:N-len(最长特殊递增序列)

write answer 切换为英文 切换为中文


转发分享