csp信奥赛C++高频考点专项训练之贪心算法 --【跳跃与过河问题】：过河问题-洪萨配资

csp信奥赛C++高频考点专项训练之贪心算法 --【跳跃与过河问题】：过河问题

题目描述

有一个大晴天，Oliver 与同学们一共N NN人出游，他们走到一条河的东岸边，想要过河到西岸。而东岸边有一条小船。

船太小了，一次只能乘坐两人。每个人都有一个渡河时间T TT，船划到对岸的时间等于船上渡河时间较长的人所用时间。

现在已知N NN个人的渡河时间T TT，Oliver 想要你告诉他，他们最少要花费多少时间，才能使所有人都过河。

注意，只有船在东岸（西岸）的人才能坐上船划到对岸。

输入格式

输入文件第一行为人数N NN，以下有N NN行，每行一个数。

第i + 1 i+1i+1行的数为第i ii个人的渡河时间。

输出格式

输出文件仅包含一个数，表示所有人都渡过河的最少渡河时间。

输入输出样例 1

输入 1

4 6 7 10 15

输出 1

说明/提示

数据范围

对于40 % 40\%40%的数据满足N ≤ 8 N\le8N≤8。

对于100 % 100\%100%的数据满足4 ≤ N ≤ 10 5 , 1 ≤ T ≤ 10 7 4\le N\le10^5,1\le T\leq 10^74≤N≤105,1≤T≤107。

样例解释

初始：东岸{ 1 , 2 , 3 , 4 } \{1,2,3,4\}{1,2,3,4}，西岸{ } \{\}{}；
第一次：东岸{ 3 , 4 } \{3,4\}{3,4}，西岸{ 1 , 2 } \{1,2\}{1,2}，时间7 77；
第二次：东岸{ 1 , 3 , 4 } \{1,3,4\}{1,3,4}，西岸{ 2 } \{2\}{2}，时间6 66；
第三次：东岸{ 1 } \{1\}{1}，西岸{ 2 , 3 , 4 } \{2,3,4\}{2,3,4}，时间15 1515；
第四次：东岸{ 1 , 2 } \{1,2\}{1,2}，西岸{ 3 , 4 } \{3,4\}{3,4}时间7 77；
第五次：东岸{ } \{\}{}，西岸{ 1 , 2 , 3 , 4 } \{1,2,3,4\}{1,2,3,4}时间7 77。

所以总时间为7 + 6 + 15 + 7 + 7 = 42 7+6+15+7+7=427+6+15+7+7=42，没有比这个更优的方案。

思路分析

这是一个经典的过河问题（Bridge and Torch Problem），目标是让所有人从东岸到西岸，船一次最多两人，耗时取较慢者，求最小总时间。

核心贪心策略（当人数 ≥4 时）：
每次将最慢的两人（c, d）送过河，有两种最优方案：

方案一：最快两人（a, b）过河 → a 返回 → 最慢两人（c, d）过河 → b 返回
耗时：a + 2*b + d
方案二：最快一人（a）带最慢（d）过河 → a 返回 → a 带次慢（c）过河 → a 返回
耗时：2*a + c + d

取较小值累加，然后去掉最慢两人，重复直到剩余人数 ≤ 3。

剩余人数处理（下标从1开始）：

1 人：t[1]
2 人：t[2]
3 人：t[1] + t[2] + t[3]

复杂度：排序 O(N log N)，模拟 O(N)，可通过 N=1e5。

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintM=100010;//最大人数intt[M];//存储过河时间intmain(){intn;cin>>n;//读入人数for(inti=1;i<=n;++i)cin>>t[i];//读入每个人的时间sort(t+1,t+n+1);//升序排序longlongans=0;//总时间while(n>3){//当人数大于3时，每次送走最慢两人ints1=t[2]+t[1]+t[n]+t[2];//方案1: a,b去; a回; c,d去; b回ints2=t[n]+t[1]+t[n-1]+t[1];//方案2: a,d去; a回; a,c去; a回ans+=min(s1,s2);//取较小值累加n-=2;//最慢两人已过河}//处理剩余≤3人if(n==1)ans+=t[1];//只剩1人elseif(n==2)ans+=t[2];//剩2人elseans+=t[1]+t[2]+t[3];//剩3人cout<<ans<<endl;//输出结果return0;}

功能分析

输入处理：使用静态数组t[M]存储时间，下标从1开始，先读取人数 N，再读取 N 个时间值存入t[1]到t[N]。
排序：对t[1]到t[N]升序排序，使t[1]为最快，t[N]为最慢。
贪心模拟：当 N>3 时，循环计算两种经典方案的耗时（方案1：t[2]+t[1]+t[N]+t[2]，方案2：t[N]+t[1]+t[N-1]+t[1]），选择较小的累加到答案中，然后 N 减少 2（去掉最慢两人）。
边界处理：剩余 1、2 或 3 人时，直接按最优方式计算时间并累加。
输出：打印最小总时间（使用long long防止溢出）。

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

【秘籍汇总】（完整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信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：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;}

csp信奥赛C++高频考点专项训练之贪心算法 --【跳跃与过河问题】：过河问题