【题解】Luogu[P6003] USACO20JAN Loan Repayment S

模拟赛第一题（

9pts

考虑暴力。

枚举 \(x\)，对于每个 \(x\)，模拟 \(k\) 天，判断其是否合法，找出最大的 \(x\)。

时间复杂度：\(O(n^2)\)

36pts

考虑优化先前暴力算法。

我们不难发现当 \(x\) 合法时，必然有合法 \(x_1\)，当且仅当 \(x_1 < x\)。
故 \(x\) 具有单调性，考虑二分答案。

对于 \(x\)，我们进行二分答案，对于每一个 \(x\)，我们对其进行判断是否合法。
其中判断合法我们每一天逐一枚举，时间复杂度 \(O(k)\)。若合法，我们便再去寻找更大的合法 \(x\)。

时间复杂度：\(O(n \log n)\)

bool check(int x) {
    int num = 0;
    for (int i = 1; i <= k; i++) {
        int y = (n - num) / x;
        if (y < m) y = m;
        num += y;
    }
    if (num >= n) return true;
    return false;
}

signed main() {
    n = read(), k = read(), m = read();
    int l = 1, r = n;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    printf("%d\n", ans);
    return 0;
}

100pts

我们发现先前算法中，check() 函数效率为 \(O(k)\)，是显然超时的，我们考虑优化 check()。

对于每个 \(y\)，我们发现，当其中的 \(x\) 固定时，存在 \(z\) 使得 \(y = \lfloor \dfrac{z}{x} \rfloor = \lfloor \dfrac{z + 1}{x} \rfloor = \dots = \lfloor \dfrac{z + a}{x} \rfloor\)

故我们可以算出其中的 \(a\)，一次将 \(a\) 个相同的 \(y\) 算出。

我们假设当前欠了 \(r\) 加仑，还有 \(t\) 天的时间去还。
那么我们对于 \(r\)，每次算出 \(a\)，判断其是否能在 \(k\) 天中还完。
我们知道若存在 \(a\)，则 \(\lfloor \dfrac{z + (a - 1)}{x} \rfloor\) 依然等于 \(\lfloor \dfrac{z + a}{x} \rfloor\)，而 \(a\) 天之后必然有 \(\lfloor \dfrac{z + a}{x} \rfloor \le \lfloor \dfrac{z + a - 1}{x} \rfloor\)。
通过计算得出 \(a = \lfloor \dfrac{r}{y} - x + 1 \rfloor\)
因为均为 int，故对于正整数 \(a\) 直接 \(a = \dfrac{r}{y} - x + 1\)

当此时 \(y <= m\) 时，因为题面说明 \(y = m\)，故可以直接算出剩余天数能还的量。

容易看出，当 \(r \le 0\) 或者 \(t == 0\) 时，就不需要进行计算。
当 \(t == 0\) 时，若 \(r \le 0\)，说明对于当前 \(x\)，能在规定时间内还完，故合法。

时间复杂度：\(O(\sqrt{n} \log n)\)

#define int long long
int n, k, m, ans;

bool check(int x) {
    int r = n, t = k;
    while (r > 0 && t) {
        int y = r / x;
        if (y <= m) r -= t * m, t = 0;
        else {
            int a = min(r / y - x + 1, t);
            r -= y * a;
            t -= a;
        }
    }
    return r <= 0;
}

int erfen(int l, int r) {
    int num = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) num = mid, l = mid + 1;
        else r = mid - 1;
    }
    return num;
}

signed main() {
    n = read(), k = read(), m = read();
    int l = 1, r = n;
    ans = erfen(l, r);
    printf("%lld\n", ans);
    return 0;
}