题目分析

题意简述

题目要求根据给定的扑克牌游戏规则，在已知扑克牌数量及每张牌点数的情况下，找到一种放置扑克牌的方法，使得在游戏中获得的总分数最小。游戏规则为：将点数为 $n$ 的牌放在标有数字 $i$ 的格子上可获得 $(n \times i)$ 分，且在某格子上放牌后会挡住其后格子的路径（即后续不能再在其后格子放牌）。输入包含多个测试用例，每个测试用例先给出扑克牌数量 $m$，再依次给出每张牌的点数，需要输出每个测试用例的最小分数。

输入

• 第一行输入整数 $n$（$n \leq 10$），表示测试用例的数量。
• 对于每个测试用例：
  • 先输入整数 $m$（$m \leq 100000$），表示扑克牌的数量。
  • 接着输入 $m$ 个整数，分别表示每张扑克牌的点数（点数范围为 $1$ 到 $13$）。

输出

对于每个测试用例，输出一行，为该测试用例能获得的最小分数。

解题思路

贪心策略

利用小顶堆（升序队列）来实现贪心算法。核心思路是每次都选取当前最小的两张牌，将它们“组合”（这里的“组合”可以理解为根据游戏规则放置牌后计算的分数相关操作），然后将组合后的结果（可以理解为新的“牌”）再放入堆中，重复这个过程，直到堆中只剩下一张“牌”（即所有牌都经过了处理）。这样做的原因是，为了使总分数最小，我们优先处理点数小的牌，因为它们在乘以格子数字（距离）时增加的分数相对较少，符合贪心算法每次选择局部最优解以达到全局最优解的思想。

具体操作

1. 初始化一个小顶堆 _queue 用于存储扑克牌的点数。
2. 对于每个测试用例：
   • 先清空堆 _queue。
   • 读取扑克牌数量 $m$ 和每张牌的点数 num，并将点数 num 依次放入堆 _queue 中。
   • 初始化结果变量 result 为 $0$。
   • 当堆中牌的数量大于 $1$ 时，执行以下操作：
     • 取出堆顶元素（当前最小的点数）赋值给 min1 并从堆中删除。
     • 再次取出堆顶元素（此时第二小的点数）赋值给 min2 并从堆中删除。
     • 将 min1 和 min2 相加的结果累加到 result 中（模拟根据游戏规则放置牌后获得的分数）。
     • 将 min1 和 min2 相加的结果放入堆 _queue 中，模拟新的“牌”加入游戏。
   • 最后输出 result，即该测试用例的最小分数。

代码实现

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
// 升序队列，小顶堆
priority_queue<int, vector<int>, greater<int> > _queue;

int main()
{
    int m, n, num;
    scanf("%d", &n);
    while (n--)
    {
        scanf("%d", &m);
        while (_queue.empty() == false) _queue.pop();
        for (int i = 0; i < m; i++)
        {
            scanf("%d", &num);
            _queue.push(num);
        }
        int result = 0;
        while (_queue.size() > 1)
        {
            int min1 = _queue.top();
            _queue.pop();
            int min2 = _queue.top();
            _queue.pop();
            result += min1 + min2;
            _queue.push(min1 + min2);
        }
        cout << result << endl;
    }
    return 0;
}

代码说明

1. 头文件和命名空间：包含了输入输出流 <iostream>、字符串处理 <cstring>、标准输入输出 <cstdio> 和优先队列 <queue> 相关的头文件，并使用 using namespace std; 引入标准命名空间。
2. 小顶堆定义：priority_queue<int, vector<int>, greater<int> > _queue; 定义了一个小顶堆 _queue，用于存储扑克牌的点数，greater<int> 表示堆中的元素按升序排列。
3. 主函数：
   • 定义变量 m 表示扑克牌数量，n 表示测试用例数量，num 表示每张牌的点数。
   • 读取测试用例数量 n。
   • 对于每个测试用例：
     • 读取扑克牌数量 m。
     • 清空堆 _queue。
     • 通过循环读取每张牌的点数 num 并放入堆 _queue 中。
     • 初始化结果变量 result 为 $0$。
     • 使用 while 循环，当堆中牌数量大于 $1$ 时，执行取堆顶元素、计算分数、将新元素放入堆等操作。
     • 最后输出 result，即该测试用例的最小分数。