编程之美 1.8 小飞的电梯调度算法
题意:
亚洲微软研究院所在的希格玛大厦一共有6部电梯。在高峰时间,每层都有人上下,电梯每层都停。
实习生小飞常常会被每层都停的电梯弄的很不耐烦,于是他提出了这样一个办法:
由于楼层并不算太高,那么在繁忙的上下班时间,每次电梯从一层往上走时,我们只允许电梯停在其中的某一层。
所有乘客从一楼上电梯,到达某层后,电梯停下来,所有乘客再从这里爬楼梯到自己的目的层。在一楼的时候,每个乘客选择自己的目的层,电梯则计算出应停的楼层。
问:电梯停在哪一层楼,能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少?
解法一:
暴力枚举法。从第1层枚举到第N层,求出电梯在x层停的话,所有乘客需要怕多少层楼。
求出最少的那层即可。
int nPerson[];//到第i层的人数 int tar=-1; for(i=1;i<=n;i++)//枚举每一层为目标层 { sum=0; for(j=1;j<i;j++) sum+=nPerson[j]*(i-j); for(j=i+1;j<=n;j++) sum+=nPerson[j]*(j-i); if(tar==-1||min>sum) { tar=i; min=sum; } }
解法二:
动态规划
假设电梯停在第x层,已知目的楼层在x层的有N2人,在x层以下的有N1人,在x层以上的有N3人。此时总花费为sum。
则往上走一层的话,i变为i+1层时,N1,N2要上走一层,N3少走层,总花费变为sum+N2+N1-N3。
则:N2+N1-N3>0,则i层比i+1层好,不必向上;
那么初始状态电梯停在第一层,向上dp,开始时N2+N1-N3<0,sum越来越小,
直到某一层N2+N1>=N3,就没有必要在往上走了。这时已求出最合适的楼层了。
int N; int nPerson[]; int target_floor=1; int min_floors=0; int N1=0,N2=nPerson[1],N3=0; for(i=2;i<=N;i++)//预处理 求N3和min { min_floors+=nPerson[i]*(i-1); N3+=nPerson[i]; } for(i=2;i<=N;i++) { if(N1+N2<N3)//上面一层好些 { target_floor=i; min_floors+=(N1+N2-N3); N1+=N2; N2=nPerson[i]; N3-=nPerson[i]; } else break; } return target_floor;
解法三:
中位数
假设只有两个人,一个去8层,一个去3层,那么不管电梯停在3至8层中间的任何楼层,
两个人的总花费都是5.就比如在数轴上点3和点8中间的任何点距离3和8的距离之后都是5。
假设有N个人,他们的目标楼层分别是2,3,3,4,5,5,5,7,7,8,9,
对于两端的(2,9)电梯只要停在他们之间都一样。同理对于(3,8)电梯只要停在他们中间都一样……,
最终电梯只要停在中间那个数即可,也就是中位数。
如果N是偶数个的话,停在中间那两个数任何一个都可以的;
int nPerson[N+1];//要停每层的人数 int target_floor; int left=1,right=N; while(right-left>1)//模拟 { while(nPerson[left]==0) //这层空,加楼层 left++; nPerson[left]--;//最低层减1人, while(nPerson[right--]==0) right--; nPerson[right]--;//最高层也减1人, } return left;
扩展问题:
1、如果往上爬楼梯比较累,往下走较容易,假设往上走一层耗费k单位的能量,往下走一层只耗费1单位的能量。
这个跟解法二动态规划一样,只是i到i+1层时,向上爬累要乘k,(N1+N2)*k-N3
只是i到i-1层,N3+N2-N1*k
所以只要把代码中(N1+N2<N3)改为 ((N1+N2)*K<N3),和相应的部分即可。
2.停k层的解法
没仔细研究:http://blog.csdn.net/a81895898/article/details/7480883