《编程之美》中“小飞的电梯调度算法”停k层的解法

Cpp代码 

1. #include <iostream>  
2. #include <time.h>  
3. #include <cassert>  
4. using namespace std;  
5.   
6. const int totalFloorNum = 10;  
7. const int totalStopNum = 4;  
8. int nPerson[totalFloorNum + 1];  
9. int minFloors[totalFloorNum + 1][totalStopNum + 1];  
10. int targetFloors[totalFloorNum + 1][totalStopNum + 1];  
11.   
12. //stopNum floors between (totalFloorNum - floor + 1)th floor and (totalFloorNum)th floor  
13. //the last stop is totalFloorNum - floor  
14. int compute(int floor, int stopNum)  
15. {  
16.     if(minFloors[floor][stopNum] >= 0)  
17.         return minFloors[floor][stopNum];  
18.   
19.     //determine the first stop in the remaining (floor) floors  
20.     int min = totalFloorNum - floor + 1;  
21.     int max = totalFloorNum + 1 - stopNum;  
22.   
23.     assert(min <= max);  
24.     //the next possible step can range from min to max  
25.     int minFloor = -1;  
26.     int targetFloor = -1;  
27.   
28.     if(stopNum == 1)  
29.     {  
30.         //if only need to stop once, just copy the code from Beauty of Programming  
31.         int n1 = 0;  
32.         int n2 = nPerson[min];  
33.         int n3 = 0;  
34.         minFloor = 0;  
35.         targetFloor = min;  
36.   
37.         for(int i = min + 1; i <= totalFloorNum; i++)  
38.         {  
39.             n3 += nPerson[i];  
40.             minFloor += nPerson[i] * (i - min);  
41.         }  
42.   
43.         for(int i = min + 1; i <= totalFloorNum; i++)  
44.         {  
45.             if(n1 + n2 < n3)  
46.             {  
47.                 targetFloor = i;  
48.                 minFloor += (n1 + n2 - n3);  
49.                 n1 += n2;  
50.                 n2 = nPerson[i];  
51.                 n3 -= n2;  
52.             }  
53.             else  
54.                 break;  
55.         }  
56.     }  
57.     else  
58.     {  
59.         for(int i = min; i <= max; i++)  
60.         {  
61.             int mid = (min - 1 + i) / 2;  
62.             int temp = 0;  
63.             if(min == 1)  
64.             {  
65.                 for(int j = 1; j < i; j++)  
66.                 {  
67.                     temp += (i - j) * nPerson[j];  
68.                 }  
69.             }  
70.             else  
71.             {             
72.                 //passengers who want to go to from (min - 1) to mid will get off at (min - 1)th floor  
73.                 for(int j = min; j <= mid; j++)  
74.                 {  
75.                     temp += (j - min + 1) * nPerson[j];  
76.                 }  
77.                 //passengers who want to go to from (mid + 1) to (i) will get off at (i)th floor  
78.                 for(int j = mid + 1; j < i; j++)  
79.                 {  
80.                     temp += (i - j) * nPerson[j];  
81.                 }  
82.             }  
83.   
84.             temp += compute(totalFloorNum - i, stopNum - 1);  
85.             if(temp < minFloor || minFloor == -1)  
86.             {  
87.                 minFloor = temp;  
88.                 targetFloor = i;  
89.             }  
90.         }  
91.     }  
92.     minFloors[floor][stopNum] = minFloor;  
93.     targetFloors[floor][stopNum] = targetFloor;  
94.     return minFloor;  
95. }  
96.   
97. int main()  
98. {  
99.     memset(nPerson, 0, (totalFloorNum + 1) * sizeof(int));  
100.     srand(time(NULL));  
101.     for(int i = 1; i <= totalFloorNum; i++)  
102.     {  
103.         nPerson[i] = rand() % 100;  
104.     }  
105.   
106.     for(int i = 1; i <= totalFloorNum; i++)  
107.     {  
108.         for(int j = 1; j <= totalStopNum; j++)  
109.         {  
110.             minFloors[i][j] = -1;  
111.         }  
112.     }  
113.   
114.     for(int i = 1; i <= totalFloorNum; i++)  
115.     {  
116.         cout <<i <<"th floor: " <<nPerson[i] <<" persons" <<endl;  
117.     }  
118.     int minFloor = compute(totalFloorNum, totalStopNum);  
119.     cout <<"The floors selected is: " <<endl;  
120.     int floor = totalFloorNum;  
121.     int stopNum = totalStopNum;  
122.     while(stopNum >= 1)  
123.     {  
124.         int selectedFloor = targetFloors[floor][stopNum];  
125.         cout <<"The " <<(totalStopNum - stopNum + 1) <<"th selected floor is: "  
126.             <<selectedFloor <<endl;  
127.         floor = totalFloorNum - selectedFloor;  
128.         stopNum--;  
129.     }  
130.     cout <<"Min floors: " <<minFloor <<endl;  
131.     system("pause");  
132. }