P8647 [蓝桥杯 2017 省 AB] 分巧克力——二分

二分

P8647

思路

cnt是记录获得巧克力的小朋友的数量
ans是巧克力的边长
找到满足cnt >= k 的，ans的最大值

代码

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
int n, k, h[N], w[N];bool check(int mid)
{long long int cnt = 0;// cnt的最大值是N * H * W = 1e15for (int i = 0; i < n; i ++ ){cnt += (h[i] / mid) * (w[i] / mid);if (cnt >= k) return true;}return cnt >= k;
}int SR(int l, int r)
{while (l < r){int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}return r;
}int main()
{cin >> n >> k;for (int i = 0; i < n; i ++ ) cin >> h[i] >> w[i];// cnt是记录获得巧克力的小朋友的数量// ans是巧克力的边长// 找到满足cnt >= k 的，ans的最大值cout << SR(1, 100000);return 0;
}

一些写题时的错误

1. mid = l + r + 1 >> 1漏了 +1