《编程之美》读书笔记04: 1.8 小飞的电梯调度算法
假设电梯有n层,上楼要消耗能量k1,下楼要消耗能量k2,用a[i]表示要在第i层下的人数,Si为到i层时已经下(包括i层)的总人数,则总人数S=Sn。若用F(i)表示电梯在i层停时要消耗的总能量,则电梯在i+1层停时,有Si人要多下一层,(S-Si)人少上一层。则:
F(i+1) = F(i) + k2*Si - k1*(S-Si) = F(i) + (k2+k1)*Si – k1*S = F(i) + G(i)
(定义G(i) = (k2+k1)*Si – k1*S)
由于Si是递增的,G(i)也是递增的,当G(i) <= 0,F(i+1) <= F(i),“求使F(i)最小的i”问题等同于 “求使G(i)=(k2+k1)*Si – k1*S <= 0的最大i值”(所得i值+1即为原问题的解),或 “求使G(i)=(k2+k1)*Si – k1*S >= 0的最小i值”(所得i值即为原问题的解)。注意:等号可取可不取。
对书上原题:k1=k2=1,G(i)=2*Si – S >= 0,可以扫描数组两遍,第一遍算出S,第二遍算出使 2*Si – S < 0 的最大i值。也可以只扫找一遍,用两个指针分别指向数组的开头和结尾,一个向前移动,一个向后移动,并同时开始计算最前几个数的和S2, i和最后几个数的和Sj, n,通过调整两个指针位置,使S2, i<= Sj, n总成立并使i尽可能的大,这样扫描完毕,
2*S2, i <= S2, i + Si+1, n = S,且 2*S2, i+1 >= S。
(书中解法二的分析与给出的代码不对应,只有证明“使N1 + N2 >= N3成立的第一个i值就是全局最优解”,才能保证给出的代码的正确性。)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
程序代码
1
//arr[i] 为在第i层要下的人数,因而i>=2;
2
int lift(int *arr, unsigned sz, int& total)
3![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
4
assert(sz>=3);
5
int i, sum=0, count=0;
6
total=0;
7![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i=2; i<sz; i++)
{
8
sum += arr[i];
9
total += arr[i]*i;
10
}
11
total = total - sum * 2;
12![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for ( i=2; ; i++)
{
13
count += arr[i] * 2;
14
if ( count >= sum ) break;
15
total += count - sum;
16
}
17
return i;
18
}
19![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
20![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
21![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
22
//arr[i] 为在第i层要下的人数,因而i>=2;
23![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
24
int lift2(int *arr, unsigned sz, int& total)
25![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
26
assert(sz>=3);
27
int *low=arr+2, *high=arr+sz-1;
28
int sum_a=0, sum_b=0, sum_ta=0, sum_tb=0;
29![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (low <= high)
{
30![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (sum_a <= sum_b)
{
31
sum_a += *low++;
32
sum_ta += sum_a;
33![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
} else
{
34
sum_b += *high--;
35
sum_tb += sum_b;
36
}
37
}
38
--low;
39
//电梯所停的那层始终被计算了,要扣除
40![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (sum_a >= sum_b)
{
41
sum_ta -= sum_a;
42![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
} else
{
43
++low;
44
sum_tb -= sum_b;
45
}
46![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
47
total = sum_ta + sum_tb;
48
return low - arr;
49
}
50![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)