社区讨论

MnZn求助一道题

学术版参与者 3已保存回复 8

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
8 条
当前快照
1 份
快照标识符
@lobdty96
此快照首次捕获于
2023/10/29 19:23
2 年前
此快照最后确认于
2023/11/04 01:03
2 年前
查看原帖
RT,有 nn 个数,你需要任选一段区间,设这段区间里不同数的个数为 xx,区间长度为 yy,要最小化 xy\frac{x}{y} 的值。 n6×104n\leq 6\times 10^4
现在已知的思路是:分数规划套线段树。
每次二分,从左到右枚举右端点,然后在前面的区间内寻找上一次这个值出现的位置,记为 prepre,则在线段树上把 pre+1pre+1ii 的位置区间加 11 ,代表这个区间内多了一个不同的数字。然后查询前 ii 个位置的最小值,套分数规划的式子。
MnZn不懂为什么是查这个的最小值,(最小值不应该出现在当前这个位置,即为大小为 11

回复

8 条回复,欢迎继续交流。

正在加载回复...