过桥

.
.
.
.
.
分析

最容易想到的一个贪心策略是：

让一个最快的人来回带人

但是显然是错误的
比如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; }

转载于:https://www.cnblogs.com/YYC-0304/p/10292828.html

总结

以上是生活随笔为你收集整理的过桥的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。