PAT 1030 完美数列 解题思路
问题描述
问题分析
题目描述很简单,就是找出一组长度最大的子数列,满足M ≤ mp。
最简单的一种思路就是遍历出所有的子数列,然后找出子数列的最大值最小值,再找出满足条件的最长子数列。但是这样每次遍历都要再循环找出数列的最大值和最小值,时间复杂度太高,肯定无法满足题目的要求。所以首先需要简化题目,将数列递增排序,这样数列最小就是第一个元素,最大就是最后一个元素,就方便找到最大最小值。
最大最小值解决了,也就是M ≤ mp这个条件解决了,下面就需要找最长了。一种思路是二层循环外层循环改变数列起始位置,内层循环改变数列结束位置,最后找出最长的数列。但这样时间复杂度很高,因此我想到了一种类似于动态规划的方法。
从起始位置开始,假设当前数列只有一个元素,因为p为正整数,所以大于等于1,肯定满足条件,然后右移一位,假设有两个数,判断是否满足不等式。如果满足那就继续后移判断;如果不满足,那之后的数都要比当前的M要大,肯定都不会满足条件,p是一个常量,所以我们要让m增大,就是让左边界右移,从而实现增大m。这里要用到动态规划的思想,我们用一个变量max记录下以当前M为结尾满足条件的最大子序列长度。若当前M满足等式,我们就让max+1;若不满足,就按刚才的思路将左边界右移,即增大最小值。伪代码如下:
1 | for(int i=0;i<array.length;++i){ |
有个地方需要仔细思考,为什么不满足条件的时候只需要将最小值左移就可以了,不需要判断当前最大值是否满足不等式或者修改当前最大长度么?
其实不需要,因为最大长度记录的是当前的M结尾的最大子数列长度,当最小值左移后,当前最大长度依然没变;紧接着又进入下一次循环,所以当前遍历的数列长度也没变。也就是说每当m右移必然存在M右移,所以每次判断的子数列长度都是当前最大数列长度。而且当m右移后,就不需要判断当前的M是否满足了,因为即便满足也比最大长度要小,因为数列有序,若后一个满足,则前一个一定满足。
最后最后,题目中还有一个坑,题中的数列、p、m、M长度都在int变量的范围内。但是判断条件要将m*p一旦m和p都比较大,很可能超出int变量的最大范围,因此在定义变量p时,应该使用无符号的int变量或者是long int等更大空间的类型。一旦超出长度就会导致测试点5错误。
解决方法
最后贴上我的解题方法,供参考。
1 | int main() { |