欢迎来到天天文库
浏览记录
ID：75521929
大小：180.75 KB
页数：28页
时间：2021-12-16
《浅谈二分策略的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、二分策略在信息学竞赛中的应用华东师大二附中杨俊12/15/20211二分策略来源一个很简单的想法——在最坏情况下排除尽可能多的干扰，以尽可能快地求得目标效率高！对信息的充分利用，尽可能去除冗余，减少了不必要计算应用广！12/15/20212三种应用类型类型一：二分查找——应用于一般有序序列类型二：二分枚举——应用于退化了的有序序列类型三：二分搜索——应用于无序序列12/15/20213类型一：二分查找——应用于一般有序序列申明：“有序序列〞，仅包含两层意思：第一，它是一个序列，一维的第二，该序列是有序的，即序列中的任意两个元素都是可以比较的，也就是拥有我们平时所说的全序关系12/
2、15/20214类型一：二分查找——应用于一般有序序列二分查找的一般实现过程：〔1〕确定查找范围〔2〕选择基准元素〔3〕关键字比较，确定更精确的范围〔4〕判断结果，如不够精确，转至〔2〕12/15/20215例一：顺序统计问题[问题描述]给定一个由n个不同的数组成的集合S，求其中第i小的元素。例如：S={3,7,2,6,8,1,5}，i=4Answer=512/15/20216问题的一般解法二分查找的过程：〔1〕确定待查找元素在S中〔2〕在n个元素中随机取出一个记为x，将x作基准〔3〕设S中比元素x小的有p个〔4〕如果找出x，输出；否那么转至〔2〕因为x是随机选出的，由简单的概率
3、分析，可得算法的复杂度期望值为O(n)。如果i<p，我们将范围确定为S中比x小的元素，求该范围内第i个元素；如果i=p，表示第i小的元素就是x如果i>p，我们将范围确定为S中比x大的元素，求该范围内第i-p-1个元素；12/15/20217小结举这个例子，是想说明两点：第一，二分查找==logn第二，二分查找==平均??12/15/20218类型二：二分枚举——应用于退化了的有序序列与类型一中的二分查找相比，最大的区别在于这里的二分在判断选择哪一个局部递归调用时没有了比较运算*。显式有序序列隐含的退化了的有序序列12/15/20219例二：BTP职业网
4、球赛[问题描述]N〔N≤65536〕—有N头奶牛〔N是2P〕参加网球淘汰赛。即N头奶牛分成N/2组，每组两头奶牛比赛，决出N/2位胜者；所有胜者继而分成N/4组比赛……直至剩下一头牛是冠军。K〔1≤K≤N-1〕—比赛既要讲求实力，又要考虑到运气。每头奶牛都有一个BTP排名，恰为1－N。如果两头奶牛的排名相差大于给定整数K，那么排名靠前的奶牛总是赢排名靠后的奶牛；否那么，双方都有可能获胜。Answer—现在观众们想知道，哪头奶牛是所有可能成为冠军的牛中排名最靠后的。并要求你列举出一个可能的比赛安排使该奶牛获胜。12/15/202110初步分析由于N很大，猜测可以通过贪心方法解决。K
5、+11K+22……2KK3K+12K+1…………12/15/202111
此文档下载收益归作者所有
