题目：洛谷 P6003

链接：洛谷，逐月

题意

• 有一个人欠了别人 \(n\) 单位牛奶，每一天他会还 \(y = \max(m, \frac{n - g}{x})\) 单位，\(g\) 为之前还的牛奶，请求出最大的 \(x\) 使得这个人在 \(k\) 天后能换至少 \(k\) 单位牛奶。

• \(1 \le n, m, k \le 10^{12}, km < n\)。

思路

暴力

首先这个题有单调性，若 \(x\) 能满足要求，那么 \(x-1\) 也行。所以可以二分 \(x\)，在模拟 \(k\) 天的情况，判断即可。

正解

• 可以发现这在很多天里，\(y\) 是相同的，如果把这些相同的合并起来，就可以降低很多的复杂度。但是怎么知道现在有多少个相同的呢，我们需要先找到需要达到要求的最小 \(n\)，也就是 \(xy\)，那么当前的 \(n - g\) 要经历多少次才会 $ < xy$ 呢，答案是 \(\lceil \frac{n - g - xy}{y} \rceil\)，所以这就达到了合并相同的 \(y\) 的效果。

• 最后判断需要的天数和 \(k\) 的大小关系即可，注意每天至少给 \(m\) 单位的细节即可。

• 但是问题来了，这能过吗，可以发现每个 \(y\) 都不一样，所以最极端的情况是 \(y = 1, 2, 3, 4, \dots\)，\(y\) 的种数只有 \(\sqrt{n}\) 级别，可以通过此题。

时间复杂度

暴力

• 二分：\(O(\log n)\)。
• 模拟：\(O(k)\)。
• 总时间复杂度：\(O(k \log n)\)。

正解

• 二分：\(O(\log n)\)。
• \(y\) 最多 \(\sqrt{n}\) 种取值，\(O(\sqrt{n})\)。
• 总时间复杂度：\(O(\log n \cdot \sqrt{n})\)。

using ll = long long;

ll n, k, m;

bool Check(ll x) {
  if (n / x < m) {
    return 0;
  }
  ll w = x * m, _n = n, c = 0;
  while (_n > w) {
    ll q = _n / x, t = x * q; // 注明一下 q 是思路中的 y
    ll s = max(1LL, (_n - t + q - 1) / q); // 增加的天数
    _n -= s * q, c += s; // _n %= q 
  }
  return (c + (_n + m - 1) / m <= k);
}

ll F() { // 二分答案
  ll l = 1, r = n;
  while(l < r) {
    ll mid = (l + r + 1) >> 1;
    if (Check(mid)) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  return l;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> k >> m;
  cout << F();
  return 0;
}