第二题
题目大意
题目给出一个长度为nnn的序列aaa,以及变量k,lk,lk,l。
kkk : 指的是你可以进行的操作次数
lll : 每次操作可以选择几个数字
操作: 你可以选择序列aaa当中的某一个数字进行+1的操作,例如你可以选择一个数字222把它变为333 。 当l=ml=ml=m的时候,意味着你可以同时指定m个数字进行+1的操作,最多可以执行kkk次
hhh : 我们自己定义出来的一个数字,hhh是否合法需要进行判断,判断的条件如下:
1. 在序列aaa当中存在hhh个大于等于hhh的数字
若满足这个条件,那么当前hhh的取值就被称之为合法的。
在你进行操作之后,序列当中可以达到的最大合法hhh为多少?
思路解析
题目既然要求我们去求出一个最大的hhh取值,我们先不管他合不合法,我们先简单的去给他列出一个范围。
我可以注意到题目当中的一个条件: 必须有hhh个大于等于hhh的数字,因此我们可以断定,h的取值最大不可能超过nnn.
我们可以关注到,h=0的时候一定是合法的,因为0≤ai≤1050 \leq a_i \leq 10^50≤ai ≤105,无论如何0都是合法的。
那么我们在这里可以发现一个特点,合法的h范围一定为从1开始到达某一个数字的连续序列,例如[1,2,3,4,5....C]且C≤n[1,2,3,4,5....C] 且 C \leq n[1,2,3,4,5....C]且C≤n。
那么我们就可以在范围[1,n][1,n][1,n]当中去寻找我们的hhh的取值。
由于我们可以修改其中某些元素的数值,使其+1,我们的目的是通过这样的操作,让更多原本没有到达h的数字变为h。
选择数字进行操作也是有优先级的,比如假如h为10,将一个数字9变为10,和将一个数字1变为10,肯定会优先选9,因为他的消耗小。而我们根据贪心原理,很明显是越多大于等于h的数字越好。
我们可以得到一个贪心原理: 优先修改较大的数字使其变为大于等于h的数字更合理。
序列是无序的,假若为了筛选较大的数字优先进行修改,我们需要使用sort排序使其变为降序,更方便我们进行计算。
更改序列的先后顺序会导致结果产生变化?不会!因为题目要求的条件为大于等于h的数字,跟他的先后顺序没有关系,因此该题的序列更改前后顺序无问题。
根据以上推理,我们来做一下伪代码
1. 枚举h的取值
2. 判断是否合法
但是在n=105n = 10^5n=105,该代码会超时,其时间复杂度为O(n2)O(n^2)O(n2)。
时间复杂度优化
列出主要的两部分内容以及目的时间复杂度
1. 枚举h的范围,找到最大的h O(n)
2. 判断h的合法性,使用操作修改数值。 O(n)
我们可以发现h的取值具有二象性,当当前h取值不合法时,变大绝对不可能找到合法的h,变小才有可能,那么我们要找的h的最大取值一定为合法区间[1,C][1,C][1,C]中的C。那么我就可以根据h是否合法,来去写一个二分查找,查找h的取值在其中的合法最值。