题解：P2942 [USACO09MAR] Moon Mooing G

题目传送门

简化题意

第一行给出 $c$ 和 $n$，第二行给出 $a_1$ 和 $b_1$ 和 $d_1$ 三个数，第三行给出 $a_2$ 和 $b_2$ 和 $d_2$ 三个数。然后用两条公式不断地迭代、计算，剔除重复的时长，取前 $N$ 个整数为 $N$ 次哞叫的时长。

也就是说，求 $a_n$ 的数值。

大致思路

首先定义数组 $a$，长度为 $n$，用来储存每一次的叫声。使得 $a_1$ 的值为 $c$。

然后使用循环迭代，每一次使用两个公式（$f_1=a_1 \times c \div d_1 + b_1$ 和 $f_2=a_2 \times c \div d_2 + b_2$）求出 $f_1$ 和 $f_2$。

f1=a1*a[m1]/d1+b1;
f2=a2*a[m2]/d2+b2;

然后，在每一次循环中，都对 $f_1$ 和 $f_2$ 进行判断。分为三种情况：

• 如果 $f_1 < f_2$，那么 $a_i$ 赋值为 $f_1$，且 $m_1$ 要加一；
• 如果 $f_1 > f_2$，那么 $a_i$ 赋值为 $f_2$，且 $m_2$ 要加一；
• 如果 $f_1 = f_2$，那么 $a_i$ 赋值为 $f_1$，且 $m_1$ 与 $m_2$ 都要加一。

if(f1<f2){
	a[i]=f1;
	m1++;
}else if(f1>f2){
	a[i]=f2;
	m2++;
}else{
	a[i]=f1;
	m1++,m2++;
}

可以化简为：

• $a_i$ 等于 $f_1$ 和 $f_2$ 中的较小值；
• 如果 $f_1 \le f_2$，那么 $m_1$ 要加一；
• 如果 $f_1 \ge f_2$，那么 $m_2$ 要加一。

a[i]=min(f1,f2);
if(f1<=f2)m1++;
if(f1>=f2)m2++;

其它内容放在代码里了。

代码实现

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll a[4000010],c,n,a1,b1,d1,a2,b2,d2,m1=1,m2=1,f1,f2;
int main(){
	cin>>c>>n>>a1>>b1>>d1>>a2>>b2>>d2;
	a[1]=c;
	for(ll i=2;i<=n;i++){
		f1=a1*a[m1]/d1+b1;
		f2=a2*a[m2]/d2+b2;
		a[i]=min(f1,f2);
		if(f1<=f2)m1++;
		if(f1>=f2)m2++;
	}cout<<a[n];
	return 0;
}