求助一道yy出来的数学题

回复帖子

@Dancing_Wave  2020-03-26 12:09 回复

这是我这个蒟蒻yy出来然后难倒了自己的题目

有一个从 $n$ 到 $1$ 的数列 $a$ ,还有一个正整数数列 $b$ ,使得 $c$ 数列满足 $c_i=a_i\times b_i$ 且单调递增。

求 $b_n$ 的最小值

请问这个题有没有比 O(n)快的方法?希望有dalao能回复我一句,谢谢!

@SSerxhs  2020-03-26 12:22 回复 举报

易证可以贪心

易证 ${b_{i+1}-b_i}$ 会越来越大

考虑枚举这个差值(差值之间的差可能大于1,可以考虑跳跃转移),复杂度大约是根号级,不会证

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。