过桥
n人过桥问题：
n个人要晚上过桥，在任何时候最多两个人一组过桥，每组要有一只手电筒。在这n个人中只有一个手电筒能用，因此要安排以某种往返的方式来返还手电筒，使更多的人可以过桥。
扯点有的没的：
这个问题是昨天算法课上老师提出来让我们写思路或者代码的，老师给的是4个人的情况，所花费的时间分别为1、2、5、10(分钟)让我们给出一个在17分钟以内可以完成的解决方案。其实最优解刚好就是17分钟，我们假设这4个人分别为A、B、C、D，策略分为以下几步：(1)A、B先过桥，花费了2分钟；(2)A回来送手电筒，花费了1分钟；(3)C、D过桥，花费了10分钟；(4)B回来送手电筒，花费2分钟；(5）A、B一起过去，花费了2分钟；因此总时间为：2+1+10+2+2=17分钟。虽然当时想到了这个最优解，但是对于更加一般性的n人过桥问题，我没有想出一个很明确的算法，回来上网一搜才发现原来是微软面试题，顺着大家的思路走了一遍，应该是解决了这个问题。
思路：
其实这道题就是贪心算法，且贪心的策略只有两种，我们取最小的那种就行了。假设当前有n个人，我们先对n个人过桥时间从小到到排序，那么我们的贪心策略是：(1)让第1个人分别带第n-1个人和第n个人过桥，主要分为以下几步：1、n过桥，花费a[n]；1回来送手电筒，花费a[1]；1、n-1过桥，花费a[n-1]；1回来，花费a[1]；那么这种策略总的用时为：a[n-1]+a[n]+2*a[1]。(2)让第1个人和第2个人先过桥，第1个人回来送手电筒，让第n、n-1个人过桥，然后第2个人回来送手电筒。这个策略的总用时为：a[n]+a[1]+2*a[2]。因此我们只需比较以上两种方法的用时，即比较a[n-1]+a[1]与2*a[2]的大小(化简)取最小的即可。对于n=3的情况，必定是1、2、3要过桥，总用时为：a[1]+a[2]+a[3]；对于n=2的情况，必定是1、2要过桥，总用时为：a[2]；n=1，直接输出a[1]。综上，我们就可以写出程序了。这个程序只输出总用时，如果想输出具体的策略，大家可自行改动。
#include<iOStream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int a[1005];
int main()
{
int sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n);
while(n>0)
{
if(n==1)
{
sum+=a[1];
break;
}
else if(n==2)
{
sum+=a[2];
break;
}
else if(n==3)
{
sum+=a[1]+a[2]+a[3];
break;
}
else
{
if(a[n-1]+a[1]<=2*a[2])//1分别带n n-1过桥
sum+=a[n]+a[n-1]+2*a[1];
else
sum+=a[n]+a[1]+2*a[2];
n-=2;
}
}
printf("%d\n",sum);
return 0;
}
相关阅读
BootStrap这类网站是怎么赢利的?技术专利费？或者，网站广告费？
https://blog.csdn.net/lsjweiyi/article/details/70879776 【题目】 输入：第一行 n ,表示有n个套娃。之后n行，每行两个整数：分别表
首先，我谈一下自己对原版hanoi问题递归公式的推导。优秀的理解网址，有图形我按照他的，也就是将A上的n个圆盘（编号从下往上是n->1）通过B
自从微信封杀朋友圈诱导分享后，运营的裂变之道开始寻求一条新出路，而私域流量成为了解决这个问题的答案。但是提到私域流量的人很多
解决sql server2008数据库安装之后，web程序80端口被占
前言： 原来电脑上的Apache一直使用正常，在安装sql server2008后，突然发现Apache无法启动，检查了一下是因为80端口被强制占用了。 解