首页
Python
Java
前端
数据库
Linux
Chatgpt专题
开发者工具箱
487b专题
CodeForces 487B Strip
题意: n(10^5)个人分组 每组最少L个人 每组的差异为组中人最大价值-最小价值 要求差异均不超过S 问最少分几组 思路: 假设已经知道组的区间[l,r]那么计算差异就是简单的rmq问题 可以用线段树搞 我们可以用dp[i]表示到i位置产生的最少组数 假设从i位置开始分一组 会影响到哪些dp呢 我们可以利用二分+rmq找到这个组最远延伸到哪里 从L到最远点这个区间的d
阅读更多...