阿里云秋招笔试题解分享0910

上午lc周赛T4不会做，已经不知道是第几次连lc都做不出了，对水平下滑怀疑人生，一开始看错题，想了十多分钟没法下手，心态崩了。。。还好先做完T2T3后回来再看发现看错题了。。第一题看成把不优秀的变优秀了

T1:1-n的排列p，pos[p[i]]=i , 给出一个长度为m的优秀数组a ，优秀的定义是pos[a[i]]<pos[a[i+1]]<=pos[a[i]]+d

要让优秀变成不优秀，要么让相邻两个交叉，要么让相邻两个超过d，取min就行了  
也就是枚举for(i=2;i<=m;i++) smin(ans,pos[a[i]]-pos[a[i-1]]),smin(ans,d-(pos[a[i]]-pos[a[i-1]]-1))，复杂度O(n)

T2:有长度为n的数组a，每次操作使得a[i]+=i ，问最少多少次使得a数组严格递增
可以知道一次操作对于每个a[i]+=i,a[i-1]+=i-1，就让他们差距了1  ,那答案就是相邻两个差距最大的，需要追的最久的
所以for(int i=2;i<=n;i++) ans=max(ans,a[i-1]-a[i]+1)  复杂度O(n),当然二分答案也行，加个log

T3: 有x个a，y个b，不能超过k个连续相同的字母，问字典序最大的一个，构造不出输出-1
考虑不可行的情况，就是x>(y+1)*k || y>(x+1)*k
接下来构造分为3个阶段，假设k=3
第一阶段 bbbabbba....  因为我们肯定希望b能尽可能放前面，而连续不超过k个就是这样
第二阶段  bbbabbba...  bbaab
第三阶段  bbbabbba... bbaab  aaabaaabaaa 
首先考虑第三阶段，此时x=(y+1)*k ，只能连续放k个a以后放个b，然后最后也是k个a结束
然后考虑第二阶段，发现想要放第3个b但是放不了就放了a，由于此时我们再放一个b，就会导致a会超过k个
所以需要放一些a然后放一个b后进入第三阶段，因为第三阶段是无可奈何的阶段，但我们此时还是想要把1个b尽可能提前
那么第二阶段进入第三阶段的条件就是当x=(y+1-1)*k时，此时可以把一个b放这里，然后后面只能按第三阶段的方法构造了。

#阿里##阿里云##笔试#