AcWing 5382. 最多的布丁
原题链接
中等
作者:
追风小小少年
,
2024-03-24 13:29:38
,
所有人可见
,
阅读 2
// 枚举+二分
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k, M, D, res;
bool check(ll mid, int i)
{
// if (n >= mid* (i - 1) * k + mid) return 1; // 为什么这样不行?:答:超过了long long 的取值范围
if (n / mid >= (i - 1) * k + 1) return 1;
else return 0;
}
int main()
{
cin >> n >> k >> M >> D;
//刚开始选择二分算法,直接求res,发现不具有二分性。因为有两个变量D和M,而D较小,则考虑枚举D的值,这里的i是指1号牛
//分的次数(1-D),然后二分求M(即res),发现具有二分性。
for (int i = 1; i <= D && (i - 1) * k + 1 <= n; i ++)
{
ll l = 1, r = M;
while(l < r)
{
ll mid = (l + r + 1) >> 1;
if (check(mid, i)) l = mid;
else r = mid - 1;
}
if (n / l <= i * k) res = max(res, l * i);
}
printf("%lld", res);
return 0;
}