端庄黄蜂

文章
4
资源
0
加入时间
2年10月24天

Gym - 101466 J. Jeronimo's List 桶排序

题意:一共n个数字(3<=n<=3e7, 0<=ai<3e7 ),给出前面的m个(3<=m<=min(100, n)),a[i] = (a[i-m] + a[i-m+1]) % MOD,q个询问(1<=q<=1e4),询问a[1,n]里的从小到大第bi大。桶排序先按照要求用a[1,m]构造出a[1,n],然后这里n == 3e7,所以如果采用快速的比较排序算法如归并排序快速排序的时间复杂度是O(nlogn)会超时,因此我们想到可以使用线性排序方法