专栏文章

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

sswate114514
P12268题解参与者 2已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@mipjcyhh
此快照首次捕获于
2025/12/03 12:57
3 个月前
此快照最后确认于
2025/12/03 12:57
3 个月前
查看原文

暴力

读完题，很容易想到这道题的解法：从队长的下标出发，向左和向右分别遍历。
CPP
#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 了…… 让我们仔细思考一下：对于每个球员 ii，球衣号码是根据与队长的相对位置来决定的。给定队长的位置，球员 ii 的球衣号码可以表示为：
val=max⁡(i−a1,ak−i)\text{val} = \max(i - a_1, a_k - i)
其中，a1a_1 和 aka_k 分别是所有比赛中队长位置的最小值和最大值。
这里的公式表示，球员 ii 与队长最远的距离，即队长在最左侧的 a1a_1 或最右侧的 aka_k 的情况下，球员 ii 与队长的距离最大。

Code

  1. c++ 代码。
CPP
#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;
}
  1. 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()

评论

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

正在加载评论...