P13797 [SWERC 2023] Programming-trampoline-athlon! 题解

imnotcfz · 2025-08-25 18:35:21 · 题解

0x01 分析

一道简单的模拟题，但本蒟蒻调这题调了一整天，心态都崩了，所以下一个章节中会有「进食后人」。

这题主要分为两个部分：计算分数和发奖牌。

计算分数

我们要去掉蹦床的一个最低分和一个最高分，也就是先将 E 数组排个序，然后求第 2 到第 5 个分数的和。

设 E' 为排序后的 E 数组，一个队伍的分数即为 \displaystyle 10\times P+\sum_{i=2}^{5} E'_i。

发奖牌

根据题目，第 i 个队伍能发到奖牌当且仅当分数严格更大的队伍数量 \le2，也就是需要计算排名。

所以我们先按分数从高到低排个序，然后用 cnt 记录这个值。

通常情况下，cnt=i。但分数一样时排名也一样，所以我们只在当前队伍分数低于上一个队伍时更新 cnt。

0x02 实现

需要注意的是题目并没有给出 n 的范围，所以建议使用动态数组 vector，但实测队伍数量不超过 10^5。

进食后人：

• 绝对禁止向燃着的酒精灯里添加酒精（动态数组 resize 后不可使用 push_back）。
• 一定要存队伍编号。

Talk is cheap, show me the code!

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int n;
struct team {
    string c;
    int score, i;

    bool operator <(team other) {
        if (score != other.score) return score > other.score;
        return i < other.i;  // 分数相同一定要按编号排序
    }
};
vector<team> v;

string c;
int p, score;
int e[11];

int main() {
  cin >> n;
  v.resize(n);  // 预先分配空间
  for (int i = 0; i < n; i++) {
    cin >> c >> p;
    for (int j = 1; j <= 6; j++) {
      cin >> e[j];
    }
    sort(e + 1, e + 7);
    score = p * 10 + accumulate(e + 2, e + 6, 0);  // 注：accumulate 出自 <numeric>，默认为求和
    v[i] = {c, score, i};  // resize 之后直接用下标访问，绝对不要用 push_back
  }
  sort(v.begin(), v.end());
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    // 分数一样排名也一样
    if (i == 0 || v[i].score < v[i - 1].score) {
      cnt = i;
    }
    // 这支队伍太菜了，可以退役了
    if (cnt > 2) {
      break;
    }
    cout << v[i].c << ' ' << v[i].score << endl;
  }
  return 0;
}