电梯调度算法
http://www.cppblog.com/jake1036/archive/2011/06/29/149720.html
n1
n2
n3
自下向上
自上向下
n1 + n2 n3
n2 + n3 n1
1 #include <iostream>
2 using namespace std;
3
4 int whichFloorDownToUp(int ps[], int n)
5 {
6 if (n <= 1)
7 {
8 return 0;
9 }
10 else if (n == 2)
11 {
12 return 1;
13 }
14 int all = 0;
15 int n1 = ps[0];
16 int n2 = ps[1];
17 int n3 = 0;
18 int retf = 1;
19
20 for (int i = 2; i != n; ++i)
21 {
22 all += ps[i] * (i - 1);
23 n3 += ps[i];
24 }
25
26 for (int i = 2; i != n; ++i)
27 {
28 if (n1 + n2 <= n3)
29 {
30 all += (n1 + n2 - n3);
31 n1 += n2;
32 n2 = ps[i];
33 n3 -= ps[i];
34 // cout << i << endl;
35 retf = i;
36 }
37 }
38 return retf;
39 }
40
41 int whichFloorUpToDown(int ps[], int n)
42 {
43 if (n <= 1)
44 {
45 return 0;
46 }
47 else if (n == 2)
48 {
49 return 1;
50 }
51 int all = 0;
52 int n3 = 0;
53 int n2 = ps[n - 1];
54 int n1 = 0;
55 int retf = n - 1;
56 for (int i = n - 2; i >= 0; --i)
57 {
58 all += ps[i] * (n - 1 - i);
59 n1 += ps[i];
60 }
61
62 for (int i = n - 2; i >= 0; --i)
63 {
64 if (n2 + n3 <= n1)
65 {
66 all += (n2 + n3 - n1);
67 n3 += n2;
68 n2 = ps[i];
69 n1 -= ps[i];
70 // cout << i << endl;
71 retf = i;
72 }
73 }
74 return retf;
75 }
76
77 int main()
78 {
79 int ps[] = {0, 5, 3, 2, 8, 9, 1, 8, 9, 2, 5, 8};
80 cout << whichFloorDownToUp(ps, sizeof (ps) / sizeof (*ps)) << endl;
81 cout << whichFloorUpToDown(ps, sizeof (ps) / sizeof (*ps)) << endl;
82 return 0;
83 }
posted on 2011-08-03 18:01
unixfy 阅读(317)
评论(0) 编辑 收藏 引用