DPS - 题解

标签与难度

标签: 模拟, 字符串处理, 格式化输出, 数学, 基础题难度: 900

题目大意喵~

主人你好呀，这道题是想让我们化身游戏数据分析师，为一场比赛中的 n 位玩家绘制伤害输出（DPS）的柱状图，是不是很有趣，喵~？

对于每一位玩家 i，我们知道他造成的伤害值 d_i。我们需要根据一个公式来计算他柱状图的“长度” s_i。

这个公式是：

s_i = \lceil 50 \times \frac{d_i}{\max_{j} d_j} \rceil

这里的 $\max_{j} d_j$ 指的是所有玩家中最高的伤害值， $\lceil x \rceil$ 是向上取整函数，意思就是把 x 向上取到最近的整数。比如 $\lceil 3.14 \rceil$ 就是 4 啦。

计算出 s_i 后，我们就要为每位玩家画一个三行的 ASCII 柱状图。举个栗子，如果一位玩家的伤害 d_i = 777，计算出的柱状图长度 s_i = 7，那么他的图表就是：

+-------+
|       |777
+-------+

第一行和第三行是 + 号，中间夹着 s_i 个 -。第二行是 | 号，中间是 s_i 个空格，然后是 |，最后紧跟着这位玩家的伤害值 d_i。

还有一个特别的规则哦！如果一位玩家的伤害是全场最高的（也就是 MVP！），我们需要在他柱状图第二行的最后一个空格位置，用一个闪亮的 * 来标记他！如果有多个并列的 MVP，他们都要得到这个荣誉标记，喵~

解题思路分析

这道题的核心就是模拟整个过程：读取数据 -> 计算 -> 格式化输出。我们可以把这个过程分解成几个清晰的步骤，就像猫咪捕猎一样，一步一步来，保证万无一失，喵~

第一步：侦察敌情——读取数据与寻找 MVP

我们的计算公式里有一个关键的值： $\max_{j} d_j$ ，也就是全场最高伤害。在不知道这个值之前，我们是无法为任何一个玩家计算他的柱状图长度 s_i 的。

所以，我们的第一个任务就是：

读入所有玩家的伤害值 d_i，并把它们存起来。用一个 std::vector<int> 就很合适，可以把它想象成一个装满小鱼干的篮子，喵~
在读取的同时，或者读取完毕后，遍历一遍我们存好的数据，找到那个最大的伤害值，我们叫它 max_damage 吧！

这个过程就像猫咪先在战场上巡视一圈，找到最强大的那个对手。

第二步：精确计算——柱状图长度 `s_i` 的秘密

找到了 max_damage 之后，我们就可以为每一位玩家计算他们的 s_i 了。公式是 $s_i = \lceil 50 \times \frac{d_i}{\max_{damage}} \rceil$ 。

这里有一个小小的陷阱哦！关于向上取整 $\lceil a/b \rceil$ ：

方法一（浮点数法）: 最直观的方法是使用浮点数进行计算，然后调用 <cmath> 库里的 ceil() 函数。代码大概是 ceil(50.0 * d_i / max_damage)。注意 50.0，这里用浮点数可以确保整个表达式是浮点数除法，而不是会丢掉小数部分的整数除法。
方法二（整数法，更推荐！）: 浮点数有时候会因为精度问题带来意想不到的麻烦。对于正整数的除法向上取整，有一个非常优雅的整数技巧，喵~ ceil(a/b) 可以等价于 (a + b - 1) / b。
- 在我们的题目里，a 就是 50 * d_i，b 就是 max_damage。
- 所以 s_i 可以用 (50LL * d_i + max_damage - 1) / max_damage 来计算。
- 注意：50 * d_i 可能会超过 int 的范围，所以我们最好使用 long long 来进行这个中间计算，写成 50LL * d_i 是个好习惯，表示我们想用 long long 类型的 50 去做乘法，这样整个表达式就会被提升到 long long，避免溢出啦！

第三步：华丽的收尾——绘制柱状图

现在我们有了每个玩家的伤害 d_i、柱状图长度 s_i，以及全局的最大伤害 max_damage。可以开始画图啦！

我们再次遍历所有玩家的数据：

对于每个玩家，我们先画第一行：输出 +，然后循环 s_i 次输出 -，最后再输出一个 + 和一个换行符。
接着是第二行，这是最关键的一行：
- 先输出 |。
- 然后，我们要输出 s_i 个字符。这里需要判断一下：
  - 前 s_i - 1 个字符总是空格。
  - 最后一个字符（第 s_i 个）要看这位玩家是不是 MVP。我们通过比较 d_i == max_damage 来判断。如果是，就输出 *；如果不是，就输出空格。
  - 当然，如果 s_i 是0，这一步就什么都不用做啦。
- 输出完 s_i 个字符后，输出 |，然后紧接着输出这位玩家的伤害值 d_i 和一个换行符。
最后是第三行，它和第一行一模一样，我们照着画就好啦。

把这三个步骤组合起来，我们就完美地完成了任务，可以去领小鱼干了，喵呜~

代码实现

这是我根据上面的思路，精心为你准备的一份代码，注释超详细的哦，希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>

// 一个辅助函数，专门用来打印一个玩家的柱状图，让主函数更整洁喵~
// damage: 玩家伤害值
// bar_length: 计算出的柱状图长度 s_i
// is_mvp: 这位玩家是不是MVP
void print_histogram(int damage, int bar_length, bool is_mvp) {
    // 1. 打印上边框
    std::cout << "+";
    for (int i = 0; i < bar_length; ++i) {
        std::cout << "-";
    }
    std::cout << "+\n";

    // 2. 打印中间的条和数值
    std::cout << "|";
    // 打印 bar_length-1 个空格
    for (int i = 0; i < bar_length - 1; ++i) {
        std::cout << " ";
    }
    // 打印最后一个字符，需要判断是不是MVP
    if (bar_length > 0) {
        if (is_mvp) {
            std::cout << "*";
        } else {
            std::cout << " ";
        }
    }
    std::cout << "|" << damage << "\n";

    // 3. 打印下边框
    std::cout << "+";
    for (int i = 0; i < bar_length; ++i) {
        std::cout << "-";
    }
    std::cout << "+\n";
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    // 题目描述中有 n 个玩家，所以我们先读入 n
    if (!(std::cin >> n) || n == 0) {
        return 0; // 如果没有输入或没有玩家，就乖乖结束
    }

    std::vector<int> damages(n);
    int max_damage = 0;

    // Pass 1: 读取所有伤害数据，并找到最大伤害值
    for (int i = 0; i < n; ++i) {
        std::cin >> damages[i];
        if (damages[i] > max_damage) {
            max_damage = damages[i];
        }
    }
    
    // 题目保证了 max_damage > 0，所以我们不用担心除以零的错误

    // Pass 2: 遍历每个玩家，计算并打印他们的柱状图
    for (int i = 0; i < n; ++i) {
        int current_damage = damages[i];

        // 使用整数技巧计算向上取整，避免浮点数精度问题
        // s_i = ceil(50 * d_i / max_damage)
        // 使用 long long 防止 50 * current_damage 溢出
        long long numerator = 50LL * current_damage;
        long long denominator = max_damage;
        int bar_length = (numerator + denominator - 1) / denominator;

        // 判断当前玩家是否为MVP
        bool is_mvp = (current_damage == max_damage);

        // 调用我们的绘图函数~
        print_histogram(current_damage, bar_length, is_mvp);
    }

    return 0;
}

复杂度分析

时间复杂度: $O(N)$ 我们主要做了两件事：
1. 第一次遍历 n 个玩家的数据来找到 max_damage，这花费了 $O(N)$ 的时间。
2. 第二次遍历 n 个玩家的数据，为每个人计算 s_i 并打印柱状图。打印每个图的时间与 s_i 成正比，但 s_i 的最大值是固定的50，所以可以看作是常数时间。因此，这一步总共花费 $O(N \times 50) = O(N)$ 的时间。总的时间复杂度就是 $O(N) + O(N) = O(N)$ ，非常高效！
空间复杂度: $O(N)$ 我们需要一个 std::vector 来存储 n 个玩家的伤害值，因为我们需要先找到最大值，然后再回来处理每个玩家。所以，我们使用的额外空间和玩家数量 n 成正比，空间复杂度是 $O(N)$ 。

知识点总结

这道题虽然简单，但是也藏着一些可爱的小知识点呢，喵~

两遍扫描法 (Two-Pass Algorithm): 这是一个很常见的算法思想。当对一个元素的处理需要依赖整个数据集的某个全局信息（比如本题的最大值）时，我们通常需要先用一次遍历来计算出这个全局信息，再用第二次遍历来完成每个元素的处理。
向上取整 (Ceiling Division): 我们学到了计算向上取整的两种方法！
- ceil() 函数 + 浮点数：直观但要注意精度。
- (a + b - 1) / b 整数技巧：在处理整数时更安全、更高效。
格式化输出: 在很多编程竞赛中，按照固定格式输出结果是一项基本功。通过循环和条件判断，我们可以精确地构造出任何想要的文本图形。
数据类型选择: 注意到 50 * d_i 可能溢出 int，从而选择 long long 进行中间计算，这是写出健壮代码的好习惯，喵~

希望这篇题解能对你有所帮助！编程就像探索一个新世界，充满了乐趣和挑战，加油哦，主人！喵~

DPS - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

第一步：侦察敌情——读取数据与寻找 MVP ​

第二步：精确计算——柱状图长度 s_i 的秘密 ​

第三步：华丽的收尾——绘制柱状图 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​