题意
有一个会重复k次的数组,每个人都可以那不超过t种礼物,礼物必须是顺序发的,不能第一个发给第二个,求最少的人的个数。
首先每一个人都必须要取尽可能多的礼物,然后按这个模拟即可。
那么我们就要搞出每一个点往后跳到那里。这个最容易想到的应该是主席树加二分,根据两只\(\log\)跑得快定律我们可以得出这是过不了的,因此我们就可以使用双指针加\(map\)。想到一个很有意思的东西,比如说我现在要对每一位都做二分,那么这个可以使用双指针解决,另一个例子就是P10282
这样我们就可以用一个map加上双指针就可以搞出跳到的位置。然后直接模拟肯定是不行的,我们可以使用倍增,像这样。然后就做完了。细节稍微注意一下