题解：P12268 [蓝桥杯 2024 国 Python B] 球衣号码

swate114514 · 2025-04-21 20:59:20 · 题解

暴力

读完题，很容易想到这道题的解法：从队长的下标出发，向左和向右分别遍历。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;

    vector<int> a(n, -1);

    while (m--) {
        int x;
        cin >> x;

        int cnt = 0;
        for (int i = x - 1; i < n; i++) {
            a[i] = max(a[i], cnt);
            cnt++;
        }

        cnt = 1;
        for (int i = x - 2; i >= 0; i--) {
            a[i] = max(a[i], cnt);
            cnt++;
        }
    }

    for (auto it : a) cout << it << ' ';

    return 0;
}

优化

很明显暴力 TLE 了…… 让我们仔细思考一下：对于每个球员 i，球衣号码是根据与队长的相对位置来决定的。给定队长的位置，球员 i 的球衣号码可以表示为：

其中，a_1 和 a_k 分别是所有比赛中队长位置的最小值和最大值。

这里的公式表示，球员 i 与队长最远的距离，即队长在最左侧的 a_1 或最右侧的 a_k 的情况下，球员 i 与队长的距离最大。

Code

1. c++ 代码。

   
   #include <bits/stdc++.h>

using namespace std;

int main() { ios::sync_with_stdio(false); cin.tie(0);

// 读取球员数和队长数
int n, m;
cin >> n >> m;

// 存储队长的位置，自动去重
unordered_set<int> s;

// 读取队长的位置
for (int i = 0; i < m; ++i) {
    int p;
    cin >> p;
    s.insert(p);
}

// 将队长的位置存入vector并排序
vector<int> p2(s.begin(), s.end());
sort(p2.begin(), p2.end());

// 获取队长位置中的最小值和最大值
int a1 = p2[0];
int ak = p2.back();

// 计算每个球员的最大球衣号码
for (int i = 1; i <= n; ++i) {
    int val = max(i - a1, ak - i); // 计算当前球员的最大球衣号码
    cout << val << ' '; // 输出，最后一个球员后换行
}

return 0;

}

2. Python 代码。
```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()

    # 读取球员数和队长数
    n = int(data[0])
    m = int(data[1])

    # 存储队长的位置，自动去重
    s = set()

    # 读取队长的位置
    index = 2
    for _ in range(m):
        p = int(data[index])
        s.add(p)
        index += 1

    # 将队长的位置存入列表并排序
    p2 = sorted(s)

    # 获取队长位置中的最小值和最大值
    a1 = p2[0]
    ak = p2[-1]

    # 计算每个球员的最大球衣号码
    result = []
    for i in range(1, n + 1):
        val = max(i - a1, ak - i)  # 计算当前球员的最大球衣号码
        result.append(str(val))

    print(' '.join(result))

if __name__ == "__main__":
    main()