本文最后更新于 741 天前,其中的信息可能已经有所发展或是发生改变。
Original Link
思想:
- 二分。
- 巧克力的边长最大为
1e5
。
- 考虑二分:
- 若当的边长满足要求,则说明还有可能取更长的边长;
- 若当前边长不满足要求,则说明当前边长不可能是最终答案;
- 当二分边界相交时即可得到最大的边长。
- 利用
pair<int, int> a[N]
存储边长数据,第 a[i]
块巧克力可分割的数量为 (a[i].first / t) * (a[i].second / t)
。
代码:
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| int n, m; |
| |
| const int N = 1e6 + 3; |
| |
| pair<int, int> a[N]; |
| |
| bool check(int t){ |
| int cnt = 0; |
| for(int i = 0; i < n; i ++){ |
| cnt += (a[i].first / t) * (a[i].second / t); |
| if(cnt >= m) return 1; |
| } |
| return 0; |
| } |
| |
| void solve(){ |
| cin >> n >> m; |
| for(int i = 0; i < n; i ++) cin >> a[i].first >> a[i].second; |
| |
| int l = 1, r = 1e5; |
| while(l < r){ |
| int mid = l + r + 1 >> 1; |
| if(check(mid)) l = mid; |
| else r = mid - 1; |
| } |
| cout << l << endl; |
| } |
| |
| int main(){ |
| solve(); |
| return 0; |
| } |