自动搬运

查看原文

来自洛谷，原作者为

	XXXL_jzl jzl小号

搬运于2025-08-24 21:43:39，当前版本为作者最后更新于2024-12-18 20:10:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题目解析

个人觉得这一题不难，但是需要对题目有一定理解。
第一次哞叫的时候，以 $c$ 秒作为初始时长。
之后的时长有两个公式
$a_1\times \frac{c}{d_1} + b_1$。
$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

#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;
}