鱼C论坛

 找回密码
 立即注册
查看: 2179|回复: 18

[已解决]二分求最长 上升/下降/不上升/不下降 子序列

[复制链接]
发表于 2022-8-9 19:26:07 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 柿子饼同学 于 2022-8-9 20:56 编辑


呃主要问题是用二分法求最长上升子序列 , 下降子序列 , 不上升子序列 , 不下降子序列 时该用哪一个
如标题 , 就是不懂什么时候用 upper_bound , 什么时候用 lower_bound
并且函数第四个参数 less<int>() 和 greater<int>() 该如何用 , 求教

最佳答案
2022-8-10 10:55:07
柿子饼同学 发表于 2022-8-9 20:55
谢谢 , 但是问题主要是不知道求  最长 上升, 下降, 不上升, 不下降 子序列  问题中这两个函数的使用

二分查找主要是用来在辅助数组里查找要替换的目标元素的,所以应该用哪个、怎么组合取决于对辅助数组性质的要求。这个要求应该是和目标一致的,即当求最长上升子序列的时候辅助数组应该时刻是一个严格递增的序列。
基于这一点,选择就很好做了。比如要让辅助数组是不下降的,就应该允许辅助数组里有重复值出现,替换的目标就应该是第一个比当前插入值大的元素;如果是(严格)上升的,就不能有重复值,替换的目标相反就应该是第一个不小于当前插入值的元素。剩下的工作就是根据需求选用功能正确的工具函数了,只要记住 lower_bound 会把与给定的值相等的元素也算作搜索结果就可以了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-8-9 19:33:09 | 显示全部楼层

回帖奖励 +3 鱼币

本帖最后由 一点点儿 于 2022-8-9 19:42 编辑

在从小到大的排序数组中,

lower_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

在从大到小的排序数组中,重载lower_bound()和upper_bound()

lower_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。


https://blog.csdn.net/u011008379/article/details/50725670
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-8-9 20:27:54 | 显示全部楼层
lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。

在从小到大的排序数组中,

lower_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

第四个参数为比较函数,仅写函数名即可

如果第四个参数传入less<int>(),排序数组要从小到大,和上面的效果相同

如果第四个参数传入greater<int>(),排序数组要从大到小

lower_bound( begin,end,num,greater<int>() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num,greater<int>() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
柿子饼同学 + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-8-9 20:50:46 | 显示全部楼层
这两个函数的区别主要在于 std::upper_bound 返回的迭代器指向第一个比给定值大的元素,而 std::lower_bound 则返回的是指向第一个不小于给定值的元素的迭代器。究竟应该使用哪个完全取决于需求,看是否接受相等的情况。
第四个参数是自定义比较函数,让该工具能够处理更复杂的序关系:可以传入自定义的函数(类函数)来为此函数定义要处理的数据的序关系(即告诉 upper_bound/lower_bound 什么叫小于,什么叫大于)。
std::less 和 std::greater 可以认为是为了方便提供的工具,它们直接调用目标类型上的 < 或 > 运算符进行比较,在“小于就是小于”或者“把大于当成小于”的情况下可以直接使用(在目标元素是 int 等已经定义了大于或小于关系的类型时),避免书写无意义代码。

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
柿子饼同学 + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

 楼主| 发表于 2022-8-9 20:54:45 | 显示全部楼层
本帖最后由 柿子饼同学 于 2022-8-9 20:58 编辑
一点点儿 发表于 2022-8-9 20:27
lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。

在从小到大的 ...


谢谢回答, 懂了
但是问题主要是不知道求  最长 上升, 下降, 不上升, 不下降 子序列  问题中这两个函数要用哪一个
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-8-9 20:55:15 | 显示全部楼层
dolly_yos2 发表于 2022-8-9 20:50
这两个函数的区别主要在于 std::upper_bound 返回的迭代器指向第一个比给定值大的元素,而 std::lower_boun ...

谢谢 , 但是问题主要是不知道求  最长 上升, 下降, 不上升, 不下降 子序列  问题中这两个函数的使用
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-8-10 08:08:32 | 显示全部楼层

回帖奖励 +3 鱼币

动态规划也行
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-8-10 08:40:25 | 显示全部楼层

回帖奖励 +3 鱼币

学习了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-8-10 08:42:19 | 显示全部楼层

哈哈就是因为 dp 慢才学的二分
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-8-10 10:55:07 | 显示全部楼层    本楼为最佳答案   

回帖奖励 +3 鱼币

柿子饼同学 发表于 2022-8-9 20:55
谢谢 , 但是问题主要是不知道求  最长 上升, 下降, 不上升, 不下降 子序列  问题中这两个函数的使用

二分查找主要是用来在辅助数组里查找要替换的目标元素的,所以应该用哪个、怎么组合取决于对辅助数组性质的要求。这个要求应该是和目标一致的,即当求最长上升子序列的时候辅助数组应该时刻是一个严格递增的序列。
基于这一点,选择就很好做了。比如要让辅助数组是不下降的,就应该允许辅助数组里有重复值出现,替换的目标就应该是第一个比当前插入值大的元素;如果是(严格)上升的,就不能有重复值,替换的目标相反就应该是第一个不小于当前插入值的元素。剩下的工作就是根据需求选用功能正确的工具函数了,只要记住 lower_bound 会把与给定的值相等的元素也算作搜索结果就可以了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-8-10 14:48:06 | 显示全部楼层
dolly_yos2 发表于 2022-8-10 10:55
二分查找主要是用来在辅助数组里查找要替换的目标元素的,所以应该用哪个、怎么组合取决于对辅助数组性质 ...

好的 , 就是如果严格上升 下降 , 就是 lower
不严格就是 upper
谢谢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-8-10 22:02:55 | 显示全部楼层

回帖奖励 +3 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-8-11 10:07:03 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-8-13 21:24:40 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-8-14 19:42:10 | 显示全部楼层

回帖奖励 +3 鱼币

666
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-8-15 09:27:11 | 显示全部楼层

回帖奖励 +3 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-8-19 19:40:04 | 显示全部楼层

回帖奖励 +3 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-8-19 20:51:56 | 显示全部楼层

回帖奖励 +3 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-8-20 08:12:58 | 显示全部楼层

回帖奖励 +3 鱼币

学习了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 17:19

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表