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输入 13 10 2 6 7输出 14输入输出样例 2输入 27 214 1 12 7 13 176 23 191输出 238说明/提示对于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≤1061 ≤ L ≤ 10 6 1 \le L \le 10^61≤L≤1060 ≤ 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_{i1}^{n} \min(a_i, L - a_i)ansmaxi1nmin(ai,L−ai)复杂度只需一次遍历输入时间复杂度 O(n)空间复杂度 O(1)可处理n ≤ 10 6 n \le 10^6n≤106的数据。代码实现#includebits/stdc.husingnamespacestd;intmain(){intn,L;// n: 人数, L: 桥长scanf(%d%d,n,L);// 读入 n 和 Lintans0;// 最终答案初始为 0// 读入每个人的位置for(inti1;in;i){inta;// 当前人的位置距左端点距离scanf(%d,a);// 计算此人到较近端点的距离inttmin(a,L-a);// 更新答案所有 min 值中的最大值if(tans){anst;}}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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}
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输入 13 10 2 6 7输出 14输入输出样例 2输入 27 214 1 12 7 13 176 23 191输出 238说明/提示对于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≤1061 ≤ L ≤ 10 6 1 \le L \le 10^61≤L≤1060 ≤ 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_{i1}^{n} \min(a_i, L - a_i)ansmaxi1nmin(ai,L−ai)复杂度只需一次遍历输入时间复杂度 O(n)空间复杂度 O(1)可处理n ≤ 10 6 n \le 10^6n≤106的数据。代码实现#includebits/stdc.husingnamespacestd;intmain(){intn,L;// n: 人数, L: 桥长scanf(%d%d,n,L);// 读入 n 和 Lintans0;// 最终答案初始为 0// 读入每个人的位置for(inti1;in;i){inta;// 当前人的位置距左端点距离scanf(%d,a);// 计算此人到较近端点的距离inttmin(a,L-a);// 更新答案所有 min 值中的最大值if(tans){anst;}}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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}
