题解：P12404 「CZOI-R3」可爱棉羊

· · 题解

这个蒟蒻切橙题用了半小时……但是不得不说，真是好题啊！

思路

我们需要计算在 T 天后被感染的小棉羊数量的最大值和最小值。为了最大化感染数量，我们需要每个被感染的小棉羊每天尽可能感染新的小棉羊。

假设每个被感染的小棉羊每天都能向左右两个方向各感染一只新的小棉羊。这样，每个感染源每天可以感染 2 只新的小棉羊。经过 T 天后，每个感染源最多可以感染 2 \times T 只新的小棉羊。因此，一共 x 个感染源在 T 天后最多可以感染 x \times 2 \times T 只新的小棉羊。需要注意的是，当这个值超过总羊数 N 时，结果应为 N。

为了最小化感染数量，我们需要尽可能减少新感染的数量。当初始感染数 x 大于 1 时，可以通过将初始感染的小棉羊连续排列，使得它们在后续的感染过程中无法扩散。例如，小棉羊们连续排列，每个小棉羊的相邻位置已被感染，因此无法感染新的小棉羊，结果保持为羊的数量 x。当 x=1 时，第一天必须感染一个相邻的小棉羊，后续无法避免感染数量变为 2。

2 & \text{if } x = 1 \\ x & \text{otherwise} \end{cases}

Code

#include <iostream>

using namespace std;

int main() {
    long long N, T, x;
    cin >> N >> T >> x;

    long long maxn = min(x * 2 * T, N);
    long long minn = (x == 1 ? 2 : x);

    cout << maxn << ' ' << minn;

    return 0;
}