【每日一题7】AcWing 1227. 分巧克力

发表于 更新于 分类于 Valine：
本文字数： 109 阅读时长 ≈ 1 分钟

Day7 AcWing 1227. 分巧克力

思路

  1. 整数二分

    • 向下取整

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
          int bsearch_1(int l, int r)
      {
          while (l < r)
          {
              int mid = l + r >> 1;
              if (check(mid)) r = mid;
              else l = mid + 1;
          }
          return l;
      }

    • 向上取整

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
          int bsearch_2(int l, int r)
      {
          while (l < r)
          {
              int mid = l + r + 1 >> 1;
              if (check(mid)) l = mid;
              else r = mid - 1;
          }
          return l;
      }

拓展

  1. AcWing 789. 数的范围
  2. AcWing 22. 旋转数组的最小数字，不具有单调性，但具有二段性
  3. AcWing 113. 特殊排序，没有单调性，但可以二分

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>

using namespace std;

typedef long long LL;
const int N = 100010;

int n, m;
int h[N], w[N];

bool check(int mid)
{
    LL res = 0;
    for (int i = 0; i < n; i ++ )
    {
        res += (LL)h[i] / mid * (w[i] / mid);
        if (res >= m) return true;
    }
    return false;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &h[i], &w[i]);

    int l = 1, r = 1e5;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    printf("%d\n", r);
    return 0;
}