2022年CSP-X复赛真题及题解（T1：独木桥）-深圳市維司達科技有限公司

2022年CSP-X复赛真题及题解（T1：独木桥）

题目描述

长度为L LL米的独木桥上有n nn个人，他们每个人都想以最快的时间离开危险的独木桥。

已知每个人在独木桥上的行走速度为 1 米每秒，每个人只要能走到独木桥的两个端点中的其中一个就可以离开独木桥。

由于独木桥的桥面宽度很窄，只能容纳一个人通过，当两个人相遇时，他们无法交错通过，只能各自调转方向，继续沿反方向行走。

给你独木桥上的人数n nn，独木桥的长度L LL，第i ii个人的初始位置到独木桥左端点的距离a i a_iai米（每个人开始的朝向未知，但他们可以根据需要随时调转行走的方向）。

请计算出所有人同时出发，全部都离开独木桥所需的最短时间。

输入格式

第一行一个整数n nn，表示人数。

第二行一个整数L LL，表示独木桥的长度（米）。

第三行输入n nn个整数a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_na1,a2,⋯,an，表示第i ii个人初始位置到独木桥左端点的距离。

输出格式

输出一行一个整数，表示所有人都离开独木桥所需的最短时间。

输入输出样例 1

输入 1

3 10 2 6 7

输出 1

输入输出样例 2

输入 2

7 214 1 12 7 13 176 23 191

输出 2

说明/提示

对于50 % 50\%50%的数据：1 ≤ n ≤ 10 3 1 \le n \le 10^31≤n≤103；

对于100 % 100\%100%的数据：1 ≤ n ≤ 10 6 1 \le n \le 10^61≤n≤106，1 ≤ L ≤ 10 6 1 \le L \le 10^61≤L≤106，0 ≤ a i ≤ L 0 \le a_i \le L0≤ai≤L。

思路分析

核心问题：给定长度为 L 的独木桥，n 个人在桥上，每个人可以随时改变行走方向（速度 1 米/秒）。当两人相遇时，他们各自反向，相当于互相穿过而不影响对方离开桥的时间。目标是所有人离开桥的最短时间。

关键转化：由于相遇反向等价于互相穿过，每个人实际上可以独立地选择一个方向（左或右），并且不会受到其他人的干扰。那么第 (i) 个人离开桥所需的时间为：

如果向左：a i a_iai秒（走到左端点）
如果向右：L − a i L - a_iL−ai秒（走到右端点）

最优策略：要使所有人的完成时间的最大值最小化，每个人应该选择对自己更近的端点，即取min ⁡ ( a i , L − a i ) \min(a_i, L - a_i)min(ai,L−ai)。因为如果某个人选择较远的端点，该人的时间就会变大，从而可能拉大整体最大值，所以不优。因此，全部离开的最短时间就是所有min ⁡ ( a i , L − a i ) \min(a_i, L - a_i)min(ai,L−ai)的最大值。

答案公式：
ans = max ⁡ i = 1 n min ⁡ ( a i , L − a i ) \text{ans} = \max_{i=1}^{n} \min(a_i, L - a_i)ans=maxi=1nmin(ai,L−ai)

复杂度：只需一次遍历输入，时间复杂度 O(n)，空间复杂度 O(1)，可处理n ≤ 10 6 n \le 10^6n≤106的数据。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intmain(){intn,L;// n: 人数, L: 桥长scanf("%d%d",&n,&L);// 读入 n 和 Lintans=0;// 最终答案，初始为 0// 读入每个人的位置for(inti=1;i<=n;i++){inta;// 当前人的位置（距左端点距离）scanf("%d",&a);// 计算此人到较近端点的距离intt=min(a,L-a);// 更新答案：所有 min 值中的最大值if(t>ans){ans=t;}}printf("%d\n",ans);// 输出最短时间return0;}

功能分析

输入处理
读取人数 n、桥长 L，然后依次读取 n 个位置坐标。
核心计算
对每个人计算min(位置, 桥长 - 位置)，即此人选择最近的端点所需的秒数。
不断更新这些秒数中的最大值，这个最大值就是所有人同时离开桥所需的最短时间。
输出结果
打印该最大值。

更多内容请关注专栏：信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}

2022年CSP-X复赛真题及题解（T1：独木桥）