Bo2SS

简单的算法，也有复杂的一面～

二分查找#

①朴素二分#

• 找一个精确对应的值

• 浮点数情况放在②、③也成立

②⭐特殊二分#

• 找 0、1 的交界处的 1

• C++ 里实际带有实现这个功能的函数
  • lower_bound、upper_bound
  • 参考关于 lower_bound () 和 upper_bound () 的常见用法-CSDN

③⭐⭐二分答案#

• 特殊二分+func (答案)
  • 根据答案才得到判断更新条件的值 func (答案)
  • 判断更新条件的值一般隐含着有序的条件
    • 所以是否 sort 跟 func 求解方便与否有关，不是必须

HZOJ-380：大统领投票（sort）#

样例输入

3
123456799
123456789132456789123456789
11111111111111

样例输出

2
123456789132456789123456789

• 思路
  • 票数很大，要作为字符串读入，使用 string 类
    • string 类重载了＞，自带字典序比较
  • 利用 struct 类，结合对应的编号
  • 利用 sort
    • 先比较长度，strlen
    • 长度一致，则使用字典序
• 代码
  • 
  • const node &a 的 & 是传引用，可以删去，但要加 const~
  • 必须判断长度，否则 53 比 12345 的字典序大
  • 索引从 1 开始，否则引入了 (0, 0)

HZOJ-381：谁拿了最多奖学金（sort）#

样例输入

4
YaoLin 87 82 Y N 0
ChenRuiyi 88 78 N Y 1
LiXin 92 88 N N 0
ZhangQin 83 87 Y N 1

样例输出

ChenRuiyi
9000
28700

• 思路

  • 奖金并列第一时，输出最早出现的
    • 所以要记录编号，sort 是不稳定的
  • 注意奖金计算规则细节即可

• 代码

• 

HZOJ-386：吃瓜群众（①）#

样例输入

5 3
1 3 26 7 15
26 99 3

样例输出

3
0
2

• 思路
  • 排序 + 朴素二分
  • 瓜的数量和编号需揉成 struct
• 代码
  • 
  • mid 计算公式，防止溢出
    • = ((long long)l + r) / 2
    • = l + (r - l) / 2
  • 没找到就输出 0，f 初始为 0

HZOJ-387：吃瓜群众升级版（②）#

样例输入

5 5
1 3 26 7 15
27 10 3 4 2

样例输出

0
5
2
4
2

• 思路
  • 抽象为一堆 0、一堆 1，找第一个为 1 的情况
  • 考虑输出 0 的情况
• 代码
  • 
  • 有两种处理输出 0 的情况
  • 000000011111111

Leetcode-278：第一个错误的版本（②）#

示例

给定 n = 5，并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。 

• 思路
  • 用特殊二分查找做
  • 000000011111111
• 代码

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;  // 版本号从1开始
        while (l != r) {
            int mid = ((long long)l + r) / 2;  // 防止溢出方式一
            // int mid = l + (r - l) / 2;  // 防止溢出方式二
            if (isBadVersion(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

HZOJ-390：原木切割（③）#

样例输入

3 8
6
15
22

样例输出

5

• 思路
  • 左界→右界：1→max (Xi)
  • 111111110000000
  • ③ = ② + func(mid)
    • func (mid)：根据 mid 求出可以切出的段数，长度 mid 是要求的答案
• 代码
  • 
  • 右界需要确定一下，输入的时候确定

HZOJ-389：暴躁的程序猿（③）#

样例输入

5 3
1
2
8
4
9

样例输出

3

• 思路
  • 距离的上下界：1→max (Xi)
    • 为了简单，直接取1 和最大的工位编号
    • 如果要精细，可以取最小和最大的工位编号之差
  • 答案→判断依据：距离→可以安排的人数
  • 111111100000
• 代码
  • 
  • 排序了才好根据距离算可安排人数
  • func()
    • 要记录上一个安排的人的位置 last
    • 求可安排的人数 s
    • 初始化：可安排人数 s 为 1，上一个安排的人的位置 last 为 num [0]

HZOJ-393：切绳子（小数③）#

样例输入

4 11
8.02
7.43
4.57
5.39

样例输出

2.00

• 思路
  • 类似原木切割，但是数据是浮点数
    • 条件、更新公式不一样
  • 确定查找的左右边界、根据答案得判断依据
• 代码
  • 
  • 浮点数二分查找
  • 直接舍掉小数点后 2 位后的数字的思路
    • 思路一：*100→转 int→除以 100.0→设置精度 %.2f
    • 思路二：-0.005→设置精度 %.2f
    • 供参考：C++ 取整：向下取整，向上取整，四舍五入取整，直接去小数点取整-CSDN
      • %.2f、都是四舍五入机制
      • 转 int：直接去掉小数点及后面的小数取整

HZOJ-82：伐木#

样例输入

4 9
20 17 15 10

样例输出

14

• 思路
  • 类似原木切割，但判断依据是切下来的木材是否满足需要的木材长度
  • 上下界：0→max ()
  • 注意数据范围很大，相加有可能溢出，所以使用long long
    • long long 要想好位置，如果想不好，可以索性全用
• 代码
  • 
  • 想清楚答案与判断依据之间的关系

HZOJ-391：数列分段#

样例输入

5 3
4
2
4
5
1

样例输出

6

• 思路
  • 最小的最大和
  • 0000000111111，找第一个 1
    • 答案（段数和）mid 小→判断依据（段数）s 多，不满足条件，对应 0
    • 答案（段数和）mid 大→判断依据（段数）s 少，算是满足条件，对应 1
    • 因为找的是最小的最大和，考虑交界处
    • ❓❗如果是找最大的最大和，就会变成 111110000 情况
  • 左右界：max (Ai)→sum (Ai)
• 代码
  • 
  • 
  • ⭐func 函数好好琢磨！
  • 注意 long long 类型

HZOJ-394：跳石头#

样例输入

25 5 2 
2
11
14
17 
21

样例输出

4

• 思路
  • 最短跳跃距离的最大值
  • 起点和终点隐含存在：min (D (i+1) - Di)→L（起点到终点的距离）
  • 111110000
    • 因为找的是最大值，越往右值越大，所以找最后一个 1
• 代码
  • 
  • 要记得存起点和终点！
  • 对遍历到终点石头但不会移走终点石头的思考
    • 可以用移走前一块石头等效

HZOJ-392：丢瓶盖#

样例输入

5 3
1
2
3
4
5

样例输出

2

• 思路
  • 与上述暴躁的程序猿一模一样！
• 代码

HZOJ-395：复制书稿#

样例输入

9 3
1 2 3 4 5 6 7 8 9

样例输出

1 5
6 7
8 9

• 思路
  • 每个人的抄书速度都一样，数字就对应时间
  • 必须连续，书不能拆分
  • 步骤
    • 第一步：求最大值，与上述的数列分段一模一样！
    • 第二步：每个人抄书的起止编号，存在数组里
      • 拿到最大值后，从后往前扫数列
        • 如果有多解，让前面的人少抄写
      • 稍有麻烦，考察代码功底
• 代码

附加知识点#

• C++ 里的 struct 为类
  • 成员访问权限默认私有，而 struct 默认公有
• sort <algorithm> 使用

int num[105];
sort(num, num + n, cmp); 

• • num：要排序的区间首地址；num + n：区间尾地址的下一地址；cmp：
  • ⭐默认是不稳定的
    • 底层使用快速排序，结合插入排序和堆排序
    • 参考C++ 一道深坑面试题：STL 里 sort 算法用的是什么排序算法？- 知乎
  • 对于 int、string：可以直接比较大小，默认从小到大排序
  • 对于自定义结构
    • 重载小于号
    • 自己写排序方法 cmp

bool cmp(node a, node b) {
  return a.x > b.x;  // 按照node里的x从大到小排序
}

思考点#

Tips#

课程速记#