本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1809 过河问题 - 洛谷【题目描述】有一个大晴天Oliver 与同学们一共N NN人出游他们走到一条河的东岸边想要过河到西岸。而东岸边有一条小船。船太小了一次只能乘坐两人。每个人都有一个渡河时间T TT船划到对岸的时间等于船上渡河时间较长的人所用时间。现在已知N NN个人的渡河时间T TTOliver 想要你告诉他他们最少要花费多少时间才能使所有人都过河。注意只有船在东岸西岸的人才能坐上船划到对岸。【输入】输入文件第一行为人数N NN以下有N NN行每行一个数。第i 1 i1i1行的数为第i ii个人的渡河时间。【输出】输出文件仅包含一个数表示所有人都渡过河的最少渡河时间。【输入样例】4 6 7 10 15【输出样例】42【核心思想】问题分析给定N NN个人每个人有过河时间T i T_iTi。只有一艘船最多载两人船划到对岸的时间等于船上渡河时间较长的人所用时间。需要让所有人过河使得总时间最短。这是一个经典的贪心策略问题关键在于每次送最慢的两个人过河时的最优方案选择。算法选择排序将所有人按过河时间从小到大排序贪心策略每次考虑送最慢的两个人过河有两种方案选择时间较短的方案方案比较方案1最快的人带手电筒送最慢的两个人过河最快和次快的人先过河t 2 t_2t2最快的人回来t 1 t_1t1最慢和次慢的人过河t i d x t_{idx}tidx次快的人回来t 2 t_2t2总时间t 2 t 1 t i d x t 2 t_2 t_1 t_{idx} t_2t2t1tidxt2方案2最快的人分别送最慢的两个人过河最快和最慢的人过河t i d x t_{idx}tidx最快的人回来t 1 t_1t1最快和次慢的人过河t i d x − 1 t_{idx-1}tidx−1最快的人回来t 1 t_1t1总时间t i d x − 1 t 1 t i d x t 1 t_{idx-1} t_1 t_{idx} t_1tidx−1t1tidxt1关键步骤读取输入N NN人数、T [ 1.. N ] T[1..N]T[1..N]每个人的过河时间排序sort(t 1, t n 1)按过河时间从小到大排序贪心送最慢的两人过河从后往前每次i d x − 2 idx - 2idx−2计算方案1时间p_1 t[2] t[1] t[idx] t[2]计算方案2时间p_2 t[idx-1] t[1] t[idx] t[1]选择较短时间ans min(p_1, p_2)边界处理剩余2人ans t[2]两人一起过河剩余3人ans t[1] t[2] t[3]最快送最慢最快回来最快和次快一起过河输出结果最少总时间a n s ansans时间/空间复杂度时间复杂度O ( N log N ) O(N \log N)O(NlogN)主要是排序复杂度空间复杂度O ( N ) O(N)O(N)存储过河时间贪心策略的核心思想局部最优选择每次送最慢的两个人过河时选择两种方案中时间较短的方案方案比较逻辑方案1适合最快和次快的人速度相近的情况方案2适合最快的人速度远快于其他人的情况边界情况处理剩余2人或3人时需要特殊处理避免死循环贪心正确性每次局部最优选择可以推导出全局最优解适用于资源调度、时间优化、配对问题等场景【算法标签】#普及plus #贪心【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN100005;intn,t[N],ans,idx;// n: 人数, t: 过河时间, ans: 总时间, idx: 当前最慢的人signedmain(){cinn;// 输入人数for(inti1;in;i)// 输入每个人的过河时间{cint[i];}sort(t1,tn1);// 按过河时间从小到大排序for(idxn;idx3;idx-2)// 每次送最慢的两个人过河{intp_1t[2]t[1]t[idx]t[2];// 方案1intp_2t[idx-1]t[1]t[idx]t[1];// 方案2ansmin(p_1,p_2);// 选择时间短的方案}if(idx2)// 如果还剩2个人{anst[2];// 最快的两人一起过}else// 如果还剩3个人{anst[1]t[2]t[3];// 特殊处理}coutansendl;// 输出最少总时间return0;}【运行结果】4 6 7 10 15 42
题解：洛谷 P1809 过河问题
发布时间：2026/6/14 13:30:32
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1809 过河问题 - 洛谷【题目描述】有一个大晴天Oliver 与同学们一共N NN人出游他们走到一条河的东岸边想要过河到西岸。而东岸边有一条小船。船太小了一次只能乘坐两人。每个人都有一个渡河时间T TT船划到对岸的时间等于船上渡河时间较长的人所用时间。现在已知N NN个人的渡河时间T TTOliver 想要你告诉他他们最少要花费多少时间才能使所有人都过河。注意只有船在东岸西岸的人才能坐上船划到对岸。【输入】输入文件第一行为人数N NN以下有N NN行每行一个数。第i 1 i1i1行的数为第i ii个人的渡河时间。【输出】输出文件仅包含一个数表示所有人都渡过河的最少渡河时间。【输入样例】4 6 7 10 15【输出样例】42【核心思想】问题分析给定N NN个人每个人有过河时间T i T_iTi。只有一艘船最多载两人船划到对岸的时间等于船上渡河时间较长的人所用时间。需要让所有人过河使得总时间最短。这是一个经典的贪心策略问题关键在于每次送最慢的两个人过河时的最优方案选择。算法选择排序将所有人按过河时间从小到大排序贪心策略每次考虑送最慢的两个人过河有两种方案选择时间较短的方案方案比较方案1最快的人带手电筒送最慢的两个人过河最快和次快的人先过河t 2 t_2t2最快的人回来t 1 t_1t1最慢和次慢的人过河t i d x t_{idx}tidx次快的人回来t 2 t_2t2总时间t 2 t 1 t i d x t 2 t_2 t_1 t_{idx} t_2t2t1tidxt2方案2最快的人分别送最慢的两个人过河最快和最慢的人过河t i d x t_{idx}tidx最快的人回来t 1 t_1t1最快和次慢的人过河t i d x − 1 t_{idx-1}tidx−1最快的人回来t 1 t_1t1总时间t i d x − 1 t 1 t i d x t 1 t_{idx-1} t_1 t_{idx} t_1tidx−1t1tidxt1关键步骤读取输入N NN人数、T [ 1.. N ] T[1..N]T[1..N]每个人的过河时间排序sort(t 1, t n 1)按过河时间从小到大排序贪心送最慢的两人过河从后往前每次i d x − 2 idx - 2idx−2计算方案1时间p_1 t[2] t[1] t[idx] t[2]计算方案2时间p_2 t[idx-1] t[1] t[idx] t[1]选择较短时间ans min(p_1, p_2)边界处理剩余2人ans t[2]两人一起过河剩余3人ans t[1] t[2] t[3]最快送最慢最快回来最快和次快一起过河输出结果最少总时间a n s ansans时间/空间复杂度时间复杂度O ( N log N ) O(N \log N)O(NlogN)主要是排序复杂度空间复杂度O ( N ) O(N)O(N)存储过河时间贪心策略的核心思想局部最优选择每次送最慢的两个人过河时选择两种方案中时间较短的方案方案比较逻辑方案1适合最快和次快的人速度相近的情况方案2适合最快的人速度远快于其他人的情况边界情况处理剩余2人或3人时需要特殊处理避免死循环贪心正确性每次局部最优选择可以推导出全局最优解适用于资源调度、时间优化、配对问题等场景【算法标签】#普及plus #贪心【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN100005;intn,t[N],ans,idx;// n: 人数, t: 过河时间, ans: 总时间, idx: 当前最慢的人signedmain(){cinn;// 输入人数for(inti1;in;i)// 输入每个人的过河时间{cint[i];}sort(t1,tn1);// 按过河时间从小到大排序for(idxn;idx3;idx-2)// 每次送最慢的两个人过河{intp_1t[2]t[1]t[idx]t[2];// 方案1intp_2t[idx-1]t[1]t[idx]t[1];// 方案2ansmin(p_1,p_2);// 选择时间短的方案}if(idx2)// 如果还剩2个人{anst[2];// 最快的两人一起过}else// 如果还剩3个人{anst[1]t[2]t[3];// 特殊处理}coutansendl;// 输出最少总时间return0;}【运行结果】4 6 7 10 15 42
