编程之美 1.8 小飞的电梯调度算法

时间：2023-02-20 08:00:14


编程之美 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层的解法


标签：

相关文章