二分与贪心专题

ch02 - 二分与贪心专题A - 删题题意在数据可以随意排列的情况下要求相邻两项差值不超过 k问最少删掉多少数策略把数值接近的凑一起先给所有数据排序。按照该要求可以把数组分成若干段每段内满足该条件但段与段之间不满足条件。需要留下最长的段其余的段都删掉B - 构建排列题意修改数组为一个排列问最少修改次数因为每个数都不同且不超过n而且长度也为n所有排列只能为1 2 3 …n。所以排好序后与对应元素的差值的绝对值加起来就是答案。C - 吃东西题意吃一堆食物的条件为 亲和力在[ai - x, ai x] 范围内问需要调整多少次亲和力才能从前往后吃完所有食物策略从前往后吃时如果当前堆食物所要求的亲和力范围 与 前面所要求的范围有交集则无需重新设置亲和力且亲和力取值更新为该交集否则需要设置一次亲和力其范围为当前堆食物的亲和力要求范围D - 项目规划题意做每个项目的前置要求为评分 a[i]做完该项目后评分变化 b[i]。问在初始项目评分为 r 时中途评分不能变负的情况下能否做完所有项目朴素的思想先做评分能升高的项目、再做评分会降低的项目如果两个项目都能获利时b 0 的部分按门槛从低到高即可如果两个项目都亏本时b 0 的部分按门槛从高到低排反例40 30 -20 25 -10按代价从小到大排反例20 18 -7 10 -3正解如果 x 排前面可行但 y 排前面能导致 x 无法执行有R x.b y.a R y.b x.a移项得y.a - x.b R x.a - y.b故有 x.a x.b y.a y.bE - 优质主题对题意有多少组合ij使得 ai aj bi bj解析移项可得(ai - bi) (aj - bj) 0若设 ci ai - bi则有 ci cj 0构建出 ci 数组枚举 i对每个 ci求 [i1, n] 范围内有多少数值 -ci 的可对 ci 数组排序二分查找。F - 拼凑字符串题意每个贴纸上有一个相同的字符串字符串长度为 n问最少需要多少个贴纸可以拼凑出目标字符串 s解析1若 x 个贴纸可以拼凑出目标字符串 s则 x 1 个贴纸也必然可以。答案具有单调性可二分答案答案范围当目标字符串 s 长度等于贴纸字符串的长度时最少需要 1 个贴纸如果 n 1则至多需要 s.size() 个贴纸检查时判断当前有 x 张贴纸时在贴纸上每个字符需要多少个上取整贴纸上总字符数是否 n注意最终字符串必须要有 n 个字符如果不够需要随便凑一下3种字符个数分别为20 7 7n6 时解析2贪心首先所有出现过的字符必然需要在贴纸上出现一次维护每个字符的总数、以及每个字符在贴纸上的数量可计算出该字符限制下需要的贴纸张数如果贴纸有剩余的内容那必然是放当前需要贴纸张数最多的字符可用大根堆维护最后的答案则为所有字符所需贴纸数量的最大值G - 找房子题意有 n 个房子部分住了人。有 k 个人和你需要入住到不同的空房子中问理想情况下离你距离最远的人的距离 x 最小是多少解析该问题是典型的二分问题模型 —— 最大值最小化问题若限定距离你最远为 x 的时候可以安排所有人和你住下那当限定调整为 x1 的时候肯定也能住下。答案具有单调性二分答案答案的可能最小值为 1住旁边可能最大值为 n-1住两端检查时枚举你住的位置必须为空然后检查前后距离你 x 个位置范围内的空位数量是否有 k1 个。此处需要查询区间内 0 的个数可以使用上节课所学前缀个数计算得到。