本文主要是介绍过桥，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
.
.
.
.
.
分析
最容易想到的一个贪心策略是：
让一个最快的人来回带人
但是显然是错误的
比如4个人：1 1 100000 100000
最快的来回带的话要：1+1+100000+1+100000=200003
但是如果先将1 1运过去的话，然后1回来,再让100000 100000一起过去，再让右边的1来回一趟，就只要1+1+100000+1+1=100004，这样显然更优
所以第一种贪心的策略显然是不合理的，下面换种贪心策略：
首先，慢的肯定是过了桥之后不回来了
就上面那种情况，我们就是先将最快的两个带过去，
然后快的一个过来，让两个慢的过去，然后让快的再来，…
然而：
如果是1 10000 10000 10000，答案又不对了(还是第一种策略优)
结合以上两点，对于最慢的两个人我们有两种处理方法就是：
1、让最快的人来回带
2、让最快的两个人过去，再让最慢的两个一起过去，这样就减少了最慢的重复计算
关于这个贪心策略的证明是：
首先，过桥速度排在第三名之后的人不可能担任送回手电筒的任务，
原因是不如速度第一和第二的人送回来得高效。这样，
当前左岸速度最慢的人过桥后就不可能再回来，
那么我们可以优先让速度慢的过河，因为其不可能返回，先过后过等效。
如此一来，就可以得到上述的贪心策略。
.
.
.
.
.
程序：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{int n,a[10000];scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+n+1);int i=n;long long ans=0,x,y;while (1){if (i==2) ans+=a[2];if (i==3) ans+=a[1]+a[2]+a[3];if (i<=3) break;x=2*a[2]+a[1]+a[i];y=a[1]+a[i]+a[1]+a[i-1]; if (x<y) ans+=x; else ans+=y;i-=2;}printf("%d",ans);return 0;
}
这篇关于过桥的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
