雁過無痕

《編程之美》讀書筆記04： 1.8 小飛的電梯調度算法

假設電梯有n層，上樓要消耗能量k₁，下樓要消耗能量k₂，用a[i]表示要在第i層下的人數，S_i為到i層時已經下（包括i層）的總人數，則總人數S=S_n。若用F(i)表示電梯在i層停時要消耗的總能量，則電梯在i+1層停時，有S_i人要多下一層，（S-S_i）人少上一層。則：  

F(i+1) = F(i) + k₂*S_i - k₁*(S-S_i) = F(i) + (k₂+k₁)*S_i – k₁*S ＝ F(i) + G(i)

（定義G(i) = (k₂+k₁)*S_i – k₁*S）

由于S_i是遞增的，G(i)也是遞增的，當G(i) <= 0，F(i+1) <= F(i)，“求使F(i)最小的i”問題等同于 “求使G(i)＝(k₂+k₁)*S_i – k₁*S  <= 0的最大i值”（所得i值+1即為原問題的解），或 “求使G(i)＝(k₂+k₁)*S_i – k₁*S  >= 0的最小i值”（所得i值即為原問題的解）。注意：等號可取可不取。

對書上原題：k₁=k₂=1，G(i)=2*S_i – S >= 0，可以掃描數組兩遍，第一遍算出S，第二遍算出使 2*S_i – S < 0 的最大i值。也可以只掃找一遍，用兩個指針分別指向數組的開頭和結尾，一個向前移動，一個向后移動，并同時開始計算最前幾個數的和S_{2, i}和最后幾個數的和S_{j, n}，通過調整兩個指針位置，使S_{2, i}<= S_{j, n}總成立并使i盡可能的大，這樣掃描完畢，

2*S_{2, i} <= S_{2, i} + S_{i+1, n} = S，且 2*S_{2, i+1} >= S。

（書中解法二的分析與給出的代碼不對應，只有證明“使N1 + N2 >= N3成立的第一個i值就是全局最優解”，才能保證給出的代碼的正確性。）

程序代碼
 1//arr[i] 為在第i層要下的人數，因而i>=2;
 2int lift(int *arr, unsigned sz, int& total)
 3{
 4  assert(sz>=3);
 5  int i, sum=0, count=0;
 6  total=0;
 7  for (i=2; i<sz; i++){
 8    sum += arr[i];
 9    total += arr[i]*i;
10  }
11  total = total - sum * 2;
12  for ( i=2; ; i++){
13    count += arr[i] * 2;
14    if ( count >= sum ) break;
15    total += count - sum;
16  }
17  return i;
18}
19
20
21
22//arr[i] 為在第i層要下的人數，因而i>=2;
23
24int lift2(int *arr, unsigned sz, int& total)
25{
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  while (low <= high){
30    if (sum_a <= sum_b){
31      sum_a += *low++;
32      sum_ta += sum_a;
33    } else{
34      sum_b += *high--;
35      sum_tb += sum_b;
36    }
37  }
38  --low;
39//電梯所停的那層始終被計算了,要扣除
40  if (sum_a >= sum_b){
41    sum_ta -= sum_a;
42  } else{
43    ++low;
44sum_tb -= sum_b;
45  }
46
47  total = sum_ta + sum_tb;
48  return low - arr;
49}
50