noip2010普及组最后一题题目

题目描述：

给定一个长度为n的数组a1,a2,...,an，以及一个整数m。定义数组的“伪最长不降子序列”长度为它的最长不降子序列的长度加上m，即：如果这个数组的最长不降子序列长度为k，则它的伪最长不降子序列长度为k+m。

现在，你可以任意改变数组中的元素，使得它的“伪最长不降子序列”长度最小。请问最小的“伪最长不降子序列”长度是多少？

输入格式：

第一行包含两个整数n，m。

第二行包含n个整数a1,a2,...,an。

输出格式：

输出一个整数，表示最小的“伪最长不降子序列”长度。

数据范围：

1≤n≤1000, 1≤m≤1000, 1≤ai≤1000

样例

输入样例： 4 1 2 1 3 2 输出样例： 3

算法

(二分+贪心) $O(nlog^2n)$

首先，我们考虑最长不降子序列的求解方法，即用二分查找的方式来求解，时间复杂度为$O(nlogn)$。

接着，我们考虑如何修改数组中的元素来使得其“伪最长不降子序列”长度最小。假设我们现在已经确定了前$k-1$个数字，且已经求出了这个前缀的最长不降子序列长度$len_{k-1}$，现在我们需要在$a_k$之前插入一个数字，使得插入后的这个前缀的最长不降子序列长度为$len_k$，且$len_k-len_{k-1}=1$。这样插入一个数字后，$m$也会多加$1$，因此，我们只需要保证所有的插入操作所增加的长度之和不超过$m$即可。

根据贪心的思想，我们优先选择那些可以使得前缀当前最长不降子序列尽可能的短的数字进行插入。也就是说，对于一个数字$a_k$，我们希望在其之前插入一个数字$a_{p_k}$，使得这个前缀的最长不降子序列长度尽可能的短，即$len_{p_k}+1=len_k$且在满足这个条件的前提下，$p_k$越小越好。

现在的问题是，对于一个数字$a_k$，如何快速找到这个数字的合适插入位置。

我们考虑维护一个长度为$i$的不降子序列的最小末尾数字$tail_i$。对于一个数字$a_k$，我们可以通过二分查找的方式，找到一个最小的位置$p$，使得$tail_p$大于等于$a_k$，然后将$a_k$插入到$p$的位置上。

C++ 代