公交車問題

問題描述

一條線路上有 n 個公交車站，假設在到達第 i 個站點之前，車上總共有 x 個乘客，過了該站點后車上總共有 y 個乘客，
司機會把 y-x 這個數(shù)字，即乘客數(shù)量變化值 d_i 記錄下來，公交車有固定的載客量 g，若有一份司機的開車日志，車上乘客數(shù)量的可能情況有多少種

輸入輸出

輸入： 第一行有兩個數(shù)字 n 和 g，分別表示站點數(shù)量及當前撤了的最大載客數(shù)量（1 <= n,g <= 1000）

第二行共 n 個數(shù)字，由空格分開，經過第 i 個公交車站后車上乘客的變化數(shù)量 d_i (-1000 <= d_i <= 1000)

輸入數(shù)據(jù)保證從總站出發(fā)時乘客數(shù)量大于等于 0

輸出：輸出一個數(shù)字，即司機從總站出發(fā)時，車上乘客數(shù)量的可能性個數(shù)。

樣例

// 樣例輸入一： 4 10 1 2 3 4 // 樣例輸出一： 1 // 樣例輸入二： 4 5 2 -1 2 1 // 樣例輸出二： 2

問題分析

繪出示意圖

按照題中信息，可以畫出如下的示意圖：

其中藍色方框表示各個站點， di 即是第 i 站點的乘客數(shù)量變化，Pi 是經過第 i 個站點后車上的乘客數(shù)量。
可以得到等式：

• P_i - P_i-1 = d_i ，其中 0 < i <= n

數(shù)學推導

由于公交車的載客量為 g，那么對于每個 Pi 而言，都會存在默認的約束條件 0 < Pi < g。

---

簡單情況：

考慮等式：P1 - P0 = d1:

對于減數(shù) P0 而言，它的取值范圍在

• [P_1min-d₁, P_1max-d₁]，

由默認的約束條件得到取值范圍：

• [0, g-d₁]，

實際上這個范圍成立的條件是 d₁ >= 0，而實際上 d₁ 可以取負值，所以 P₀ 的取值范圍應該修正為

• [max(0, -d₁), min(g-d₁, g)];

對于被減數(shù) P₁ 而言，同樣可以得到其取值范圍在

• [max[0, d₁], min(g+d₁, g)]`。

---

推廣到一般情況：

對于所有作為減數(shù)的 P_j (0 <= j < n)，它的取值范圍是

• [max(0, -d_j+1), min(g-d_j+1, g)]；

而對于所有作為被減數(shù)的 P_k (0 < k <= n)，它的取值范圍是

• [max(0, d_k), min(g+d_k, g)]。

---

Pi-1 取最大范圍 [0, g]

在第 1 站到終點站之間的 P_i，即可以與 P_i-1 關聯(lián)的等式中作為被減數(shù)，又可以與 P_i+1 關聯(lián)的等式作為減數(shù)，因此是可以得到兩個取值范圍的，取其交集，得 P_i (0 < i < n)的范圍是

• [max(0, -d_i+1, d_i), min(g, g-d_i+1,, g+d_i)];

特殊的如 P₀ 范圍：[max(0, -d₁), min(g-d₁, g)]； 或 P_n 范圍：[max(0, d_n), min(g+d_n, g)]。

---

從 P0 的范圍開始迭代計算

然而以上利用 P_i-P_i-1=d_i 對 P_i 范圍進行的推導是建立在把 P_i-1 的取值范圍當作靜態(tài)的 [0, g] 而得出的 P_i 范圍，實際上 P_i-1 的范圍可能比靜態(tài)的 [0, g] 要小。

若已經求得 P_i-1 的范圍是 [R1, R2] （0 <= R1 <= R2 <= g），那么作為被減數(shù)的 P_i 的取值范圍應為：

• [R1+d_i, R2+d_i]

與上面得到的 P_i 的取值范圍取交集，得到：

• [max(0, R1+d_i, -d_i+1), min(g, R2+d_i, g-d_i+1)]

由于 P₀ 的范圍是確定的 [max(0, -d1), min(g-d1, g)]，因此通過上式可以遞歸算出 P_i 的取值范圍。

結果推導

通過數(shù)學分析推導，若得出 Pi 的范圍為 [R_iMin, R_iMax]，那么第 i 個站點后的人數(shù)可能情況就為

R_iMax - R_iMin + 1

取這些情況中值最小的那個，就是公交車經過整條路線時的人數(shù)變化的可能情況，也就是從總站出發(fā)時的人數(shù)可能情況。

主要代碼

推導出數(shù)學公式后，編寫代碼就非常容易了。主要代碼如下：

int tmpMax = carSize, tmpMin = 0;// 算出 P0 的最小最大值 person[0*2] = getMax(0, -diff[0]); person[0*2+1] = getMin(carSize, carSize - diff[0]);// 迭代算出 P1 - Pn-1 的最小最大值 for(int i = 1; i < station; i++) {tmpMin = person[(i-1)*2];tmpMax = person[(i-1)*2+1];person[i*2] = getMax( 0, tmpMin + diff[i-1], -diff[i] );person[i*2+1] = getMin( carSize, tmpMax + diff[i-1], carSize - diff[i] ); }// 算出 Pn 的最小最大值 tmpMin = person[(station-1)*2]; tmpMax = person[(station-1)*2+1]; person[station*2] = tmpMin + diff[station-1]; person[station*2+1] = tmpMax + diff[station-1];

這段代碼用到的最大最小值的求值公式就是由上述數(shù)學推導而來。

其它的解法

上述數(shù)學推導用到的方法是迭代求取范圍，最開始思考這個題的時候的思路是假設 P_i-1 都取最大范圍 [0, g]，使用以下公式：

遍歷所有可能去到的 k 和 j，利用 P_j 的范圍求出 P_k 的范圍，相應的代碼雖然能夠解出，但是并不好理解，執(zhí)行效率比前面所說的迭代方法低。以下是之前版本代碼的主要部分：

int tmp = 0, tmpMax = carSize, tmpMin = 0; tmp = carSize - d_i[0]; if( tmp < carSize ) {person[1] = tmp; }for(int gap = 1; gap < station; gap++) {for(int i = gap; i < station + 1; i++) {tmpMax = person[(i-gap)*2+1] + personChanged(i-gap, i);tmpMin = person[(i-gap)*2] + personChanged(i-gap, i);if( i < station) {// 最后一個計算的時候沒有額外的約束條件了tmp = carSize - d_i[i];tmpMax = getMin(tmp, tmpMax); // 取較小的（即取交集）}if( tmpMax < tmpMin ) {// 若上限小于下限，對應的不等式不成立,說明不存在這種情況cases = 0;return;}tmpMax = getMin(tmpMax, carSize);person[i*2+1] = getMin(person[i*2+1], tmpMax);tmpMin = getMax(0, tmpMin);person[i*2] = getMax(person[i*2], tmpMin);} }

總結

這個問題其實比較簡答，思考的時候需要緊緊抓住 P_i 的定位，即它到底是作為減數(shù)還是被減數(shù)來求得范圍的，否則就容易陷入思維誤區(qū)，無法快速得到計算范圍的公式。

改進的版本 和 原始的版本 都可以在 GitHub 上獲得。

轉載于:https://www.cnblogs.com/brifuture/p/9289144.html

總結

以上是生活随笔為你收集整理的公交车情况数问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。