当前位置：首页 > article >正文

东方博宜25年1月-B组（才俊）- 农田作物

article 2025/1/30 23:09:14

题目描述

科学家们正在研究一种高效的种植方法。他们发现，如果一片农田上的作物总数符合某种特定的规则，就能够大幅提升作物的产量。具体来说，农田中的每一块地所种植作物总数的因子，必须是特定的数字。
因子的候选数值包括：2，3 和 5。科学家定义，当一块农田种植作物总数的所有质因子均在这三个数的范围内时，这片农田的种植方案被称为“优质组合”。
例如，种植 60 株植物的方案是优质组合，因为它可以表示为 2^2 ×3×5，种植 1000 株植物的方案也是优质组合，因为它可以表示为 2^3 ×5^3 。
按照从小到大排序后，前十五个符合要求的种植总数依次为：1,2,3,4,5,6,8,9,10,12,15,16,18,20,24。（1 较为特殊，它没有质因子，因此也特别的认为是符合要求的）
现在，给定一个整数 N，请你帮忙计算按照从小到大排序后，第 N 个符合要求的种植总数。

输入
输入一个整数 N。

输出
输出一个正整数，表示第 N 符合要求的种植总数量。

样例
输入
18
输出
30
输入
50
输出
243
输入
500
输出
937500

说明
数据范围
对于 30% 的数据，满足 1≤N≤100。
对于 60% 的数据，满足 1≤N≤500。
对于 100% 的数据，满足 1≤N≤1500。

为了求解这个问题，我们需要生成所有符合“优质组合”定义的正整数，这些整数的质因子仅限于 2、3 和 5。我们可以使用一种类似于广度优先搜索（BFS）的策略来生成这些数字。

解题思路：

优质组合定义：定义为其质因子只能是 2、3 和 5 的正整数。
生成过程：
- 从 1 开始，使用一个最小堆（优先队列）来维持当前已找到的优质组合。
- 每次从堆中取出最小的数字，将这个数字乘以 2、3 和 5 后生成新的数字，并将它们加入堆中（如果它们还没有被加入过）。
- 使用一个集合来避免重复的数字。
排序：由于我们使用优先队列，取出的数字自然是按升序排列的。
输出第 N 个组合：在生成过程中，只需记录到第 N 个数字即可。

代码

以下是 C++ 的代码实现：

#include <iostream>
#include <queue>
#include <set>

using namespace std;

int main() {
    int N;
    cin >> N;

    // 使用优先队列存储优质组合
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    set<long long> seen; // 用于记录已经看到的数字

    pq.push(1); // 从1开始
    seen.insert(1);

    long long current = 1; // 当前的优质组合

    for (int i = 0; i < N; ++i) {
        current = pq.top(); // 取出当前最小的优质组合
        pq.pop();

        // 生成新的组合
        for (int factor : {2, 3, 5}) {
            long long new_val = current * factor;
            if (seen.find(new_val) == seen.end()) { // 确保没有重复
                pq.push(new_val);
                seen.insert(new_val);
            }
        }
    }

    cout << current << endl; // 输出第 N 个优质组合
    return 0;
}

代码解释：

输入处理：读取一个整数 N。
优先队列：使用 priority_queue 来存储并自动排序优质组合。
集合：通过 set 来确保添加到队列中的数字是唯一的。
生成数字：
- 从队列中取出最小元素 current，然后乘以 2、3 和 5 生成新的组合。
- 若新生成的组合尚未存在于集合中，则将其添加到队列和集合中。
输出：经过 N 次迭代，最终取出的 current 即为第 N 个优质组合。