Bo2SS

Bo2SS

2 二分專題

簡單的算法,也有複雜的一面~

二分查找#

①樸素二分#

  • 找一個精確對應的值
兩種情況整數浮點數
while 條件L <= RR - L > 0.00001
精確到小數點後4
更新參數更新公式更新公式
mid(L + R) / 2
為了避免溢出👇
((long long) L + R) / 2
L + (R - L) / 2
(L + R) / 2
Lmid + 1mid
Rmid - 1mid
  • 浮點數情況放在②、③也成立

②⭐特殊二分#

  • 找 0、1 的交界處的 1
兩種情況000000111111111111100000
while 條件L != R 或者 L < R
(不能是 L <= R,不會有 L> R 的情況)
同左
更新參數更新公式更新公式
mid(L + R) / 2(L + R + 1) / 2
(避免遇到 1 0 死循環)
Lmid + 1mid
(mid 可能是答案)
Rmid
(mid 可能是答案)
mid - 1

③⭐⭐二分答案#

  • 特殊二分+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
  • 思路
    • 類似原木切割,但是數據是浮點數
      • 條件、更新公式不一樣
    • 確定查找的左右邊界、根據答案得判斷依據
  • 代碼

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:
    • ⭐默認是不穩定的
    • 對於 int、string:可以直接比較大小,默認從小到大排序
    • 對於自定義結構
      • 重載小於號
      • 自己寫排序方法 cmp
bool cmp(node a, node b) {
  return a.x > b.x;  // 按照node裡的x從大到小排序
}
  • 圖片

思考點#

Tips#


課程速記#

載入中......
此文章數據所有權由區塊鏈加密技術和智能合約保障僅歸創作者所有。