zBlog

贪心算法 贪心算法是从问题的初始状态出发，通过若干次的贪心选择而得到的最优值（或较优 值）的一种求解问题的策略，即贪心策略。 贪心算法的特点 贪心选择 所谓贪心选择是指应用同一规则，将原问题变为一个相似的但规模更小的子问题，而后 的每一步都是当前看似最佳的选择，且这种选择只依赖于已做出的选择，不依赖于未做 出的选择。 2.最优子结构 执行算法时，每一次得到的结果虽然都是当前问题的最优解（即局部最优解），但只有 满足全局最优解包含局部最优解时，才能保证最终得到的结果是最优解。 几个简单的贪心案例 最优装载问题 给 n 个物体，第 i 个物体重量为 wi，选择尽量多的物体，使得总重量不超过 C。 2.部分背包问题 有 n 个物体，第 i 个物体的重量为 wi，价值为 vi，在总重量不超过 C 的情况下让总价值 尽量高。每一个物体可以只取走一部分，价值和重量按比例计算。 3.乘船问题 有 n 个人，第 i 个人重量为 wi。每艘船的载重量均为 C, 最多可乘两个人，求用最少的 船装载所有人的方案。 贪心算法的经典应用1.选择不相交区间问题 给定 n 个开区间$[a ...

Day 1这个鬼比赛只有一天，还分什么day1、day2 前序一早起床，倒腾了一下服务器，总算把Apache2 phpmyadmin什么的都安装好了，把wordpress也部署好了，便驱车前往南洋中学，还好有点关系，可以把车停在学校内部的地下停车场，不得不说，这个学校的地下空间利用的是挺充分的，停车场和每个楼都是相通的，佩服。 相遇从学校里面出来，外面成群成片的人都在玩手机、玩游戏走了不远就碰见一群骚货站在一起，其中不乏有哲学家——傅秋莱，还有我们的Van。 最迟到的是ZP背着很骚的包迟迟到了校门口。、 寻位校门终于开放，成群的人走进了大门，我们在幕布处拍了集体照便分别前往比赛区域了… 位置找了很久都没有找到，地下的食堂很大啊； 好不容易找到了部署好环境了，比赛而就开始了额。 编写刚开始不是很慌，悠悠哉哉地写着代码，到后来只有我没有做完，于是慌慌张张张地写完代码，选择了其中几个比较好实现的功能，随便乱写了一点，就过去答辩了。 答辩我们派出了Van进行答辩，Van精湛的吹牛逼技巧带领我们走向了胜利，然而，这个比赛的奖项到现在都没有出来 完了

二分法常见模型 二分查找（基础） 二分答案（重点） 代替三分(*) 注：*为扩展内容 二分答案概念二分答案，就是二分枚举答案，由于进行二分，所以时间复杂度 O(二分次数*单次判定时间复杂度)。 二分答案与二分查找类似，即对有着单调性的答案进行二分，确定可能的答案后，配合贪心、DP 等其他算法检验这个答案是否合理，不断缩减范围，最终确定答案的方法。常见的检验算法如穷举、贪心、搜索、动态规划、图论、数据结构等，可以看到，二分答案问题很好地结合了其他算法知识，非常受命题者欢迎。答案的单调性大多数情况下可以转化为一个函数，其单调性证明多种多样，如下： 移动石头的个数越多，答案越大(NOIP2015跳石头) 前 i 天的条件一定比前 i + 1 天条件更容易(NOIP2012 借教室) 满足更少分配要求比满足更多的要求更容易(NOIP2010 关押罪犯) 满足更大最大值比满足更小最大值的要求更容易(NOIP2015 运输计划) 时间越长，越容易满足条件(NOIP2012 疫情控制) 可以解决的常见问题 求最大的最小值(NOIP2015跳石头) 求最小的最大值（NOIP2010 关押罪犯）。 ...