社区讨论
MnZn求助一道题
学术版参与者 3已保存回复 8
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 8 条
- 当前快照
- 1 份
- 快照标识符
- @lobdty96
- 此快照首次捕获于
- 2023/10/29 19:23 2 年前
- 此快照最后确认于
- 2023/11/04 01:03 2 年前
RT,有 个数,你需要任选一段区间,设这段区间里不同数的个数为 ,区间长度为 ,要最小化 的值。 。
现在已知的思路是:分数规划套线段树。
每次二分,从左到右枚举右端点,然后在前面的区间内寻找上一次这个值出现的位置,记为 ,则在线段树上把 到 的位置区间加 ,代表这个区间内多了一个不同的数字。然后查询前 个位置的最小值,套分数规划的式子。
MnZn不懂为什么是查这个的最小值,(最小值不应该出现在当前这个位置,即为大小为 吗
回复
共 8 条回复,欢迎继续交流。
正在加载回复...