首页 > 其他分享 >CF1939C

CF1939C

时间:2024-04-17 21:12:13浏览次数:18  
标签:map 搞出 可以 CF1939C 指针 礼物

题意

有一个会重复k次的数组,每个人都可以那不超过t种礼物,礼物必须是顺序发的,不能第一个发给第二个,求最少的人的个数。

首先每一个人都必须要取尽可能多的礼物,然后按这个模拟即可。

那么我们就要搞出每一个点往后跳到那里。这个最容易想到的应该是主席树加二分,根据两只\(\log\)跑得快定律我们可以得出这是过不了的,因此我们就可以使用双指针加\(map\)。想到一个很有意思的东西,比如说我现在要对每一位都做二分,那么这个可以使用双指针解决,另一个例子就是P10282
这样我们就可以用一个map加上双指针就可以搞出跳到的位置。然后直接模拟肯定是不行的,我们可以使用倍增,像这样。然后就做完了。细节稍微注意一下

标签:map,搞出,可以,CF1939C,指针,礼物
From: https://www.cnblogs.com/wuhupai/p/18141781

相关文章