题解：P11886 「Stoi2025」爱你没差

题目理解

我们有一个长度为 n 的序列 a，每次可以选择两个数 x 和 y，将它们合并为 x + y。如果满足 m * x >= y 且 m * y >= x，则得一分。最终将所有数合并成一个数，求最大得分。

初步思路

问题分析：
- 每次合并两个数，得分条件是 m * x >= y 且 m * y >= x。
- 目标是最大化得分。
关键点：
- 合并的顺序会影响得分。
- 需要找到一种合并策略，使得满足得分条件的合并次数最多。

贪心策略

为了最大化得分，我们应该优先合并满足得分条件的数对。具体来说，我们可以按照以下步骤进行：

排序：将序列 a 从小到大排序。
合并：每次选择最小的两个数 x 和 y，如果它们满足 m * x >= y 且 m * y >= x，则合并它们并得一分；否则，只合并它们但不得分。

具体实现

排序：将序列 a 排序。
合并：使用一个优先队列（最小堆）来维护当前序列中的数，每次取出最小的两个数进行合并。

代码实现

CPP

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<unsigned long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 排序
    sort(a.begin(), a.end());

    // 使用优先队列（最小堆）
    priority_queue<unsigned long long, vector<unsigned long long>, greater<unsigned long long>> pq(a.begin(), a.end());

    int score = 0;
    while (pq.size() > 1) {
        unsigned long long x = pq.top(); pq.pop();
        unsigned long long y = pq.top(); pq.pop();

        if (m * x >= y && m * y >= x) {
            score++;
        }

        pq.push(x + y);
    }

    cout << score << "\n";

    return 0;
}

代码解释

输入处理：
- 读取 n 和 m。
- 读取序列 a。
排序：
- 将序列 a 从小到大排序。
优先队列：
- 使用优先队列（最小堆）来维护当前序列中的数。
合并操作：
- 每次取出最小的两个数 x 和 y，检查是否满足得分条件。
- 如果满足，则得分加一。
- 将 x + y 放回优先队列。
输出结果：
- 输出最大得分。

复杂度分析

时间复杂度：
- 排序的时间复杂度为 O(n log n)。
- 每次合并操作的时间复杂度为 O(log n)，总共进行 n - 1 次合并操作。
- 总时间复杂度为 O(n log n)。
空间复杂度：
- 使用优先队列，空间复杂度为 O(n)。

总结

通过贪心策略和优先队列，我们成功解决了这个问题。这道题目考察了贪心算法的应用能力，同时也提醒我们在实际生活中要合理规划资源，最大化收益！希望这篇题解能帮助你更好地理解题目，也希望你在编程的道路上越走越远！

题解：P11886 「Stoi2025」爱你没差

文章操作

题目理解

初步思路

贪心策略

具体实现

代码实现

代码解释

复杂度分析

总结

相关推荐

评论

题解：P11886 「Stoi2025」爱你没差