首页 > 代码库 > 【Luogu2942】哞哞叫

【Luogu2942】哞哞叫

2024-09-27 16:13:39   215人阅读

点此进入原题

算法：队列模拟

题解：

这题我一开始使用优先队列（STL中的priority_queue）来做，结果WA+TLE。其实本题只要用数组进行简单的模拟即可。当然也用到了队列的思想。

这题做的人不是很多（因为这题是老师给我们做的），但是有不少题目都是与此题高度相似（不一一列举了），所以这个思想还是很重要的

代码：

#include <cstdio>
#include <iostream>
typedef unsigned long long ull; //注意本题要用unsigned long long。
const int N = 4000000; 
ull a[N+5]; //这里我们将a数组看成一个队列
inline ull mn(ull x, ull y) {
    return x < y ? x : y;
}
int main() {
    int c, n, a1, b1, d1, a2, b2, d2, i = 1, f1 = 1, f2 = 1;
    scanf("%d%d%d%d%d%d%d%d", &c, &n, &a1, &b1, &d1, &a2, &b2, &d2);
    a[i++] = c; //初始元素c入队
    while(i <= N) {
        ull x = mn(a1*a[f1]/d1+b1, a2*a[f2]/d2+b2); //取F1()和F2()中的较小值
        a[i++] = x; //将该较小值入队
        if(x == a1*a[f1]/d1+b1) f1++; //如果较小值来自F1()，则将F1()的指针f1+1。
        if(x == a2*a[f2]/d2+b2) f2++; //如果较小值来自F2()，则将F2()的指针f2+1
    } //重点理解while循环的内容。因为算出的F1()或F2()的数据单调递增，所以可以用这样的方式生成整个数列
    std::cout << a[n]; //最后输出即可。
    return 0;
}
//祝各位早日AC此题！

 

【Luogu2942】哞哞叫


联系
我们