分析

二分+分块。

普通的二分 TLE 就在 ok 函数中。

bool ok(long long x)
{
	long long sum = 0;
	for(long long i = 1;i<=k;i++)
	{
		int s = (n-sum)/x;
		if(s<=m)
		{
			sum+=m*(k-i+1);
			break;
		}
		sum+=s;
	}
	return sum>=n;
}

所以就可以用分块来优化。

我们知道，一定有一段时间还了 $y$ 加仑，不妨把这个天数直接求出来。

设现在还的牛奶有 $sum$ 加仑，那么对于每个合法的 $sum$，有 $y=\dfrac{n-sum} {x}$，而直到 $x\times y$ 的 $sum$，都会还 $y$ 加仑，所以共还 $\dfrac {n-sum-x\times y}{y+1}$ 天。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,m,l,r,ans;
bool ok(ll x)
{
	ll sum = 0;
	for(ll i = 0;i<k;)
	{
		ll y = (n-sum)/x;
		if(y<=m)
			return (sum+(k-i)*m)>=n;
		ll add = (n-sum-x*y)/y+1;
		sum+=y*add;
		i+=add;
 	}
	return sum>=n;
}
int main()
{
	cin>>n>>k>>m;
	l = 1,r = n;
	while(l<=r)
	{
		ll mid = (l+r)/2;
		if(ok(mid))
			ans = mid,l = mid+1;
		else r = mid-1;
	}
	cout<<ans;
	return 0;
}