题解：P2942 [USACO09MAR] Moon Mooing G
XXXL_jzl
·
·
题解
题目传送门
题目解析
个人觉得这一题不难，但是需要对题目有一定理解。\
第一次哞叫的时候，以 c 秒作为初始时长。\
之后的时长有两个公式 \
$a_2\times \frac{c}{d_2} + b_2$。\
每一次选择其中较小的一项放入数组，最后输出数组的第 $n$ 项。
特别的，如果两项为一样的，在随意放入一项的同时 $ans_1,ans_2$ 都要加一。
### 具体做法
首先可以看到，时间 $1 < N < 4 \times 10^6$ 所以，将暴力枚举的方法 pass 掉（当然，不包括打表）。\
但正是这一个数据范围，让我看到了一线生机。\
可以采用模拟的方法，模拟。\
模拟从 $1$ 到 $n$ 次的哞叫时长。\
定义两个变量 $ans_1,ans_2$ 初值为 $1$。\
将数组的第一位数字初值赋值为 $c$ 用 while 循环从 $2$ 到 $n$ 进行遍历。\
如果 $f_1>f_2 \to ans_1+1$ 将 $f_1$ 放入数组。\
如果 $f_2>f_1 \to ans_2+1$ 将 $f_2$ 放入数组。\
如果两数相等，像上文说的 $ans_1+1,ans_2+1$ 将 $f_1,f_2$ 任意一个放入数组。\
在上述操作中，有一点要注意，我们用于存储位数的 $i$ 每一次都要加一，直到 $i = n$ 就可以输出结果。
### AC Code
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
//定义题目中所给的变量
int n, c;
int timing[5000010];// timing[i] 表示第i次哞叫时长
int f1, f2, ans1, ans2;
int a1, a2, b1, b2, d1, d2;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
// 先按题目要求输入
cin >> c >> n;
cin >> a1 >> b1 >> d1 >> a2 >> b2 >> d2;
// 初始化
memset(timing, 0, sizeof timing);
// 更改一下首位值
timing[1] = c;
ans1 = ans2 = 1;
int i = 1;
while(i != n) {
// 题目中所给公式
// timing[ans1] 和 timing[ans2] 为上一次存储的哞叫声长度
f1 = a1 * timing[ans1] / d1 + b1;
f2 = a2 * timing[ans2] / d2 + b2;
if(f1 < f2) timing[++i] = f1, ans1++;
else if(f1 > f2) timing[++i] = f2, ans2++;
else timing[++i] = f1, ans1++, ans2++;
// cout << timing[i] << ' ' << ans1 << ' ' << ans2 << '\n';
}
// 据题意排序
sort(timing + 1, timing + n + 1);
cout << timing[n] << '\n';
return 0;
}
```