P1809 过河问题（贪心解法讲解）

前言

这是题目

看起来是不是非常简单^~^

可它居然有绿！！！

我感觉很高（花了30多分钟写贪心解法）

OK 接下来我们开始讲解

讲解

先看代码

#include <bits/stdc++.h> using namespace std; int a[100005]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } int s=0; sort(a+1,a+n+1); while(n>=4){ if(2*a[2]+a[1]+a[n]>=2*a[1]+a[n-1]+a[n]){ s+=a[1]*2+a[n-1]+a[n]; } else{ s+=a[2]*2+a[1]+a[n]; } n-=2; } if(n==1){ s+=a[1]; } if(n==2){ s+=max(a[1],a[2]); } if(n==3){ s+=a[1]+a[2]+a[3]; } cout<<s; return 0; }

分析

有 N 个人要过河，船每次最多载 2 人，过河时间由船上较慢的人决定。目标是找到所有人过河的最短总时间。

思路

将所有人按过河时间从小到大排序后，考虑每次送最慢的两个人过河。有两种策略：

1. 策略A：最快的两个人先过河，最快的回来，最慢的两个人过河，次快的回来
   • 时间 = a[1] + 2*a[2] + a[n]
2. 策略B：最快和最慢的先过河，最快的回来，最快和次慢的过河，最快的回来
   • 时间 = 2*a[1] + a[n-1] + a[n]

解析

1. 排序：sort(a+1,a+n+1)将时间从小到大排序
2. 主循环：while(n>=4)当人数≥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人）
3. 剩余情况处理：
   • n==1：只剩1人，直接过河（其实这个可以不写）
   • n==2：2人一起过河，取较慢的时间
   • n==3：3人一起过河（最快的来回接送）

结尾

相信你一定听懂了

bye bye