编程之美:小飞的电梯调度算法-阿里云开发者社区

开发者社区> 人工智能> 正文

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

简介: 一.问题描述    亚洲微软研究院所在的希格玛大厦一共有6部电梯。在高峰时间,每层都有人上下,电梯每层都停。实习生小飞常常会被每层都停的电梯弄的很不耐烦,于是他提出了这样一个办法: 由于楼层并不算太高,那么在繁忙的上下班时间,每次电梯从一层往上走时,我们只允许电梯停在其中的某一层。

一.问题描述 

  亚洲微软研究院所在的希格玛大厦一共有6部电梯。在高峰时间,每层都有人上下,电梯每层都停。实习生小飞常常会被每层都停的电梯弄的很不耐烦,于是他提出了这样一个办法: 由于楼层并不算太高,那么在繁忙的上下班时间,每次电梯从一层往上走时,我们只允许电梯停在其中的某一层。所有乘客从一楼上电梯,到达某层后,电梯停下来,所有乘客再从这里爬楼梯到自己的目的层。在一楼的时候,每个乘客选择自己的目的层,电梯则计算出应停的楼层。

  问:电梯停在哪一层楼,能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少?

二.算法描述  

  方法一:暴力枚举,时间复杂度O(N^2)

 1 /*
 2  * O(N^2)
 3  */
 4 const int N = 5;
 5 int num[N+1];
 6 int ans;
 7 int min = INT_MAX;
 8 
 9 for(i = 1;i<=N;i++)
10 {
11     int sum = 0;
12     for(j = 1;j<=N;j++)
13     {
14         sum += num[j] * abs(j - i);
15     }
16     if(sum < min)
17     {
18         min = sum;
19         ans = i;
20     }
21     return (ans);
22 }

  

  方法二:书上提供的O(N)的动态规划的算法。

  假设电梯停在i层楼,可以计算出所有乘客要爬楼层的层数为Y,假设此时有N1个乘客在i层楼以下,N2个乘客在I层楼,N3个乘客在I层楼以上,则当电梯停在i+1层的时候,N1+N2个乘客要多下一层楼,共多下N1+N2层,N3个乘客要少往上面爬一层楼,少上N3层楼,此时Y(i+1) = Y(i) + N1+N2-N3,很显然,当N1+N2<N3的时候,Y不断减小。Y1很容易算出来,另外我们还可以看出,N1+N2是递增的,N3是递减的,所以N1+N2一旦大于N3的时候,我们直接退出循环即可,没有必要再计算下去了。

  

 1 /*
 2   O(N)  dp
 3  */
 4 #include <iostream>
 5 #include <cstring>
 6 using namespace std;
 7   
 8 const int N = 5;
 9 int num[N+1];
10 
11 int solve()
12 {
13     int ans = 1;
14     int min = 0;
15     int N1 = 0,N2 = num[1],N3 = 0;
16     for(int i = 2;i<=N;i++)
17     {
18         //由于只要最小值即可,所以不必用数组保存;使用数组时不用知道N1+N2 < N3)就行 
19         min += num[i] * (i-1);
20         N3 +=num[i];
21     }
22     
23     for(int i = 2;i<=N;i++)
24     {
25         if(N1+N2 < N3)
26         {
27             ans = i;
28             min +=(N1+N2-N3);
29     
30             N1 +=N2;
31             N2 = num[i];
32             N3 -=num[i];
33         }
34         else
35             break;
36     }
37     return ans;
38 }
39 
40 int main()
41 {
42     int i,j,k;
43     num[1] = 6;
44     num[2] = 2;
45     num[3] = 4;
46     num[4] = 9;
47     num[5] = 8;
48     int ans = solve();
49     cout<<ans<<endl;
50     while(1);
51     return 0;
52 }
53     

  方法三:中位数

  其实这道题目仔细分析起来就是求一组数据的中位数而已。假设两人,分别到3层楼和8层楼下,在3和8之间取一点,使得到两个点距离最小,很显然,在3和8中的每一点到3和8的距离之和都是相等的。推广到2 3

5 5 6 7 8 8 9这样一组数据,ans为中位数。

数组a存储下标,数组b存储相应人数,按b从小到大排序并交换a(或者用结构体),最后的中位数是不对的

  

 1 /*
 2  * mid_value
 3  */
 4  // 这种方法貌似是对的 
 5 #include <iostream>
 6 #include <cstring>
 7 using namespace std;
 8   
 9 const int N = 5;
10 int num[N+1];
11 
12 int solve()
13 {
14     int left = 1,right = N;
15     while(right-left >= 1)
16     {
17         while(num[left] == 0)left++;
18         num[left] --;
19         while(num[right] == 0)right--;
20         num[right] --;
21     }
22     return left;
23 }
24 
25 int main()
26 {
27     int i,j,k;
28     num[1] = 6;
29     num[2] = 2;
30     num[3] = 4;
31     num[4] = 9;
32     num[5] = 8;
33     int ans = solve();
34     cout<<ans<<endl;
35     while(1);
36     return 0;
37 }

三.结束语 

  扩展问题:往上爬一层要耗费K个单位的能量,往下走耗费1个单位的能亮,只需要计算N1+N2-N3变成N1+N2-N3*K即可。其余的都是一样的。

  扩展问题:2个有序数组求合并后的中位数,貌似是算法导论上的,有空再写……

   你让我安心什么什么,说话却吞吞吐吐,岂非存心让我不安

版权声明:本文首发在云栖社区,遵循云栖社区版权声明:本文内容由互联网用户自发贡献,版权归用户作者所有,云栖社区不为本文内容承担相关法律责任。云栖社区已升级为阿里云开发者社区。如果您发现本文中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,阿里云开发者社区将协助删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章