B2160 病人排队

chen_zhe · 2025-05-28 14:27:38 · 题解

欢迎报名洛谷网校，期待和大家一起进步！

本题考察结构体，排序。

我们使用结构体存储每位病人的信息：字符串 id 表示病人的 ID，整数 ag 表示病人的年龄，整数 rk 表示登记顺序（越小越早）：

struct P {
    string id;
    int ag;
    int rk;
};

本题的关键在于排序规则。对于第 i 个人和第 j 个人来说：

• 如果 i 不是老年人，而 j 是老年人，则需要交换；
• 如果 i,j 都是老年人，则当下列：
  • 两个条件满足其一，则需要交换；

使用冒泡排序的参考代码：

for (int i = 1; i <= n-1; ++i) {
    for (int j = 1; j <= n-i; ++j) {
        bool sw = false;
        bool sen1 = (a[j].ag >= 60);
        bool sen2 = (a[j+1].ag >= 60);
        if (sen2 && !sen1)
            sw = true;
        else if (sen1 && sen2) {
            if (a[j].ag < a[j+1].ag) sw = true;
            else if (a[j].ag == a[j+1].ag && a[j].rk > a[j+1].rk)
                sw = true;
        }
        if (sw)
            swap(a[j], a[j+1]);
    }
}

如果使用 sort 进行结构体排序，则参考的自定义比较函数如下：

bool cmp(P x, P y) {
    bool sx = (x.ag >= 60);
    bool sy = (y.ag >= 60);
    if (sx != sy) return sx;
    if (sx && sy) {
        if (x.ag != y.ag) return x.ag > y.ag; 
        return x.rk < y.rk;
    }
    return x.rk < y.rk;
}