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

· · 题解

题意已经很简洁了不再赘述。

思路：

考虑最多时，先假设有无数只绵棉羊。因为一只棉羊只能传染左右其中一只，所以第一轮传染时只能传染其中一边，假设没有重复感染，第二轮开始可以向左右两个方向扩散（除非左右没有棉羊），所以一只棉羊 T 轮传染后共有 T \times 2 只生病的棉羊。又因为有 x 个棉羊，共有 T \times 2 \times x 只棉羊被传染。因为一共只有 n 只棉羊，所以最多有 \min(T\times 2 \times x,n) 只棉羊被传染。

再考虑最少，一只棉羊可以被重复感染，那就要尽可能使它们被重复感染，这样可以使被感染的棉羊最少。所以我们把 x 只生病的棉羊放在一起，由于随机向左向右传染，所以直接当成它们互相传染即可。特别的，当 x=1 时，它必须传染给另一只相邻的棉羊。所以答案为 \max(2,x)。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
int n,t,x;
signed main(){
    IOS;
    cin>>n>>t>>x;
    cout<<min(2*t*x,n)<<" "<<max(2ll,x);
    return 0;
}

记录。