A. AI Project Development 题解

题意

Maxim 和 Nikita 一起完成一个项目，项目一共需要写至少 n 行代码。

Maxim 从一开始就工作，每小时写 x 行代码。

Nikita 有两种选择：

• 不使用 AI，从一开始每小时写 y 行代码；
• 先花 z 小时配置 AI，这段时间不写代码，之后每小时写 10 * y 行代码。

Nikita 在开始前决定是否使用 AI，之后不能改变选择。

如果项目在某个小时中间完成，这一小时也要完整计入。

要求输出项目完成所需的最少完整小时数。

思路

分别计算 Nikita 不使用 AI 和使用 AI 的完成时间，答案取最小值。

情况一：不使用 AI

此时 Maxim 和 Nikita 从一开始一起写代码。

每小时总共可以写：

x + y

所以完成项目需要：

ceil(n / (x + y))

小时。

情况二：使用 AI

Nikita 前 z 小时都在配置 AI，不写代码。

这段时间里只有 Maxim 在写代码，因此前 z 小时最多可以写：

x * z

行。

1. AI 配置完成前项目已经完成

如果：

n <= x * z

说明 Maxim 在 Nikita 配置 AI 的过程中就已经完成项目。

此时所需时间为：

ceil(n / x)

2. AI 配置完成后项目仍未完成

否则，前 z 小时后还剩：

n - x * z

行代码。

之后 Maxim 和 Nikita 一起工作，每小时总速度为：

x + 10 * y

因此使用 AI 的总时间为：

z + ceil((n - x * z) / (x + 10 * y))

向上取整

由于时间按完整小时计算，需要使用向上取整。

对于整数 a 和 b：

ceil(a / b) = (a + b - 1) / b

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int ceil_div(int a, int b) {
    return (a + b - 1) / b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n, x, y, z;
        cin >> n >> x >> y >> z;

        int no_ai = ceil_div(n, x + y);

        int use_ai;
        if (n <= x * z) {
            use_ai = ceil_div(n, x);
        } else {
            int rest = n - x * z;
            use_ai = z + ceil_div(rest, x + 10 * y);
        }

        cout << min(no_ai, use_ai) << '\n';
    }

    return 0;
}

复杂度分析

每个测试用例只需要常数次计算。

时间复杂度：O(t)
空间复杂度：O(1)