洛谷 P6003 总结

xhr0817-blog / 2023-06-05 / 原文

题目：洛谷 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;
}