专栏文章

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

iimnotcfz
P13797题解参与者 6已保存评论 9

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
9 条
当前快照
1 份
快照标识符
@mio524h4
此快照首次捕获于
2025/12/02 13:29
3 个月前
此快照最后确认于
2025/12/02 13:29
3 个月前
查看原文
题目 P13797 作者 imnotcfz

0x01 分析

一道简单的模拟题，但本蒟蒻调这题调了一整天，心态都崩了，所以下一个章节中会有「进食后人」。
这题主要分为两个部分：计算分数和发奖牌。

计算分数

我们要去掉蹦床的一个最低分和一个最高分，也就是先将 EE 数组排个序，然后求第 22 到第 55 个分数的和。
设 E′E' 为排序后的 EE 数组，一个队伍的分数即为 10×P+∑i=25Ei′\displaystyle 10\times P+\sum_{i=2}^{5} E'_i。

发奖牌

根据题目，第 ii 个队伍能发到奖牌当且仅当分数严格更大的队伍数量 ≤2\le2，也就是需要计算排名。
所以我们先按分数从高到低排个序，然后用 cntcnt 记录这个值。
通常情况下，cnt=icnt=i。但分数一样时排名也一样，所以我们只在当前队伍分数低于上一个队伍时更新 cntcnt。

0x02 实现

需要注意的是题目并没有给出 nn 的范围，所以建议使用动态数组 vector，但实测队伍数量不超过 10510^5。
进食后人：
  • 绝对禁止向燃着的酒精灯里添加酒精（动态数组 resize 后不可使用 push_back）。
  • 一定要存队伍编号。
Talk is cheap, show me the code!
CPP
#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;
}

评论

共 9 条评论，欢迎与作者交流。

正在加载评论...