题解：P15328 [GCPC 2025] Around the Table

jlhj · 2026-05-11 19:58:02 · 题解

题目概述

左边有 l \ge 2 个孩子排队，右边有 r \ge 1 个孩子排队。左右两队队首匹配，匹配后跑到对尾。

思路分析

可以发现不同的匹配总数只与人数差值 c = l - r 有关。对于每个 c 有 3 种情况，需要分类讨论。

分类讨论

• 若 c = 1，则每一种配对只出现 1 次，故总数为 l + r。
• 若 c \in \{0, 2\}，则有 \frac{3}{2} \times (l + r) 种配对。
• 若 c \notin \{0, 1, 2\}，则每种配对出现了 2 次，故总数为 2 \times (l + r)。

注：如果对分类讨论有疑惑，请务必回头观看人数差值的定义。

代码实现

注意！由于以下代码中人数的和乘 \frac{3}{2} 已经超过 int 范围，故要开 long long。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll l, r, c; // c 为人数差值
int main() {
    cin >> l >> r;
    c = l - r;
    if (c == 1) { // 左比右多 1
        cout << l + r;
    }
    else if (c == 0 || c == 2) { // 左与右一样或左比右多 2
        cout << (l + r) * 3 / 2;
    }
    else { // 差值不属于集合 {0, 1, 2}
        cout << 2 * (l + r);
    }
    return 0;
}

复杂度分析

由于没有执行任何循环，只进行了普通的加减与判断，故时间复杂度为 O(1)。