前言这是题目看起来是不是非常简单^~^可它居然有绿我感觉很高花了30多分钟写贪心解法OK 接下来我们开始讲解讲解先看代码#include bits/stdc.h using namespace std; int a[100005]; int main(){ int n; cinn; for(int i1;in;i){ cina[i]; } int s0; sort(a1,an1); while(n4){ if(2*a[2]a[1]a[n]2*a[1]a[n-1]a[n]){ sa[1]*2a[n-1]a[n]; } else{ sa[2]*2a[1]a[n]; } n-2; } if(n1){ sa[1]; } if(n2){ smax(a[1],a[2]); } if(n3){ sa[1]a[2]a[3]; } couts; return 0; }分析有 N 个人要过河船每次最多载 2 人过河时间由船上较慢的人决定。目标是找到所有人过河的最短总时间。思路将所有人按过河时间从小到大排序后考虑每次送最慢的两个人过河。有两种策略策略A最快的两个人先过河最快的回来最慢的两个人过河次快的回来时间 a[1] 2*a[2] a[n]策略B最快和最慢的先过河最快的回来最快和次慢的过河最快的回来时间 2*a[1] a[n-1] a[n]解析排序sort(a1,an1)将时间从小到大排序主循环while(n4)当人数≥4时每次送2人过河比较两种策略的时间消耗选择较小的if(2*a[2]a[1]a[n]2*a[1]a[n-1]a[n])如果策略A≥策略B选择策略B否则选择策略A每次循环 n-2送走2人剩余情况处理n1只剩1人直接过河其实这个可以不写n22人一起过河取较慢的时间n33人一起过河最快的来回接送结尾相信你一定听懂了bye bye