擺渡車

問題描述

有?n?名同學要乘坐擺渡車從人大附中前往人民大學，第?i?位同學在第?ti
分鐘去等車。只有一輛擺渡車在工作，但擺渡車容量可以視為無限大。
擺渡車從人大附中出發、把車上的同學送到人民大學、再回到人大附中（去接其他同學），這樣往返一趟總共花費?m分鐘（同學上下車時間忽略不計）。
擺渡車要將所有同學都送到人民大學。??
凱凱很好奇，如果他能任意安排擺渡車出發的時間，那么這些同學的等車時間之和最小為多少呢？??
注意：擺渡車回到人大附中后可以即刻出發。
輸入格式
第一行包含兩個正整數?n，m，以一個空格分開，分別代表等車人數和擺渡車往返一趟的時間。??
第二行包含?n個正整數，相鄰兩數之間以一個空格分隔，第?i?個非負整數?ti?代表第?i個同學到達車站的時刻。
輸出格式
輸出一行，一個整數，表示所有同學等車時間之和的最小值（單位：分鐘）。
數據范圍
n≤500,　m≤100,　0≤ti≤4?10⁶
輸入樣例：
5 1
3 4 4 3 5
輸出樣例：
0
輸入樣例：
5 5
11 13 1 5 5
輸出樣例
４
說明/提示
【輸入輸出樣例 1 說明】
同學 1 和同學 4 在第 3 分鐘開始等車，等待 0 分鐘，在第 3 分鐘乘坐擺渡車出發。擺渡車在第 4 分鐘回到人大附中。
同學 2 和同學 3 在第 4 分鐘開始等車，等待 0 分鐘，在第 4 分鐘乘坐擺渡車 出發。擺渡車在第5 分鐘回到人大附中。
同學 5 在第 5 分鐘開始等車，等待 0 分鐘，在第5 分鐘乘坐擺渡車出發。自此 所有同學都被送到人民大學。總等待時間為 0。
【輸入輸出樣例 2 說明】
同學 3 在第 1 分鐘開始等車，等待 0 分鐘，在第 1 分鐘乘坐擺渡車出發。擺渡 車在第 6 分鐘回到人大附中。
同學4 和同學 5 在第 5 分鐘開始等車，等待1 分鐘，在第 6 分鐘乘坐擺渡車 出發。擺渡車在第 11 分鐘回到人大附中。
同學 1 在第 11 分鐘開始等車，等待 2 分鐘；同學 2 在第 13 分鐘開始等車， 等待 0 分鐘。他/她們在第 13 分鐘乘坐擺渡車出發。自此所有同學都被送到人民大學。 總等待時間為 4。
可以證明，沒有總等待時間小于 4 的方案。

解決方案

線性ＤＰ
需要壓縮決策空間，減少無效狀態轉移，降低時間復雜度
也可以考慮斜率優化，維護一個下凸包。此題的斜率是時刻ｉ，單調遞增，可以使用單調的隊列優化，將計算決策點 fi 的時間復雜度降為Ｏ(1)
其它知識點：前綴和
動態方程：f[i]=min ( (cnt[i]?cnt[j])×i?(sum[i]?sum[j])+f[j] ) 其中j≤i?m

代碼

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm>using namespace std;const int maxt = 4e6 + 9;int n, m, te , ti; int ans = 0x7f7f7f7f; int c[maxt],s[maxt];//c記錄人數　ｓ記錄總時刻　　前綴和用 int f[maxt];//f(i) 無窮小時刻到ｉ時刻 范圍內的最小等車代價 int main(){scanf("%d%d",&n,&m);//n people,m 往返時間for(int i = 1; i <= n; i ++){scanf("%d",&ti);te = max(te,ti);//te　ｉｓ最后一位 c[ti] ++;s[ti] += ti;} for(int i = 1; i <= te + m-1; i ++){s[i] = s[i-1] + s[i];c[i] = c[i] + c[i-1];}for(int i = 0; i <= te + m - 1; i ++){if (i >= m && c[i - m] == c[i]) { f[i] = f[i - m]; continue; } // 壓縮無效空間.f[i] = c[i] * i - s[i];//負無窮到ｉ時刻 ,給ｆｉ賦初始值for(int j = max(0,i -m* 2 + 1); j <= i - m; j ++)//減去無用轉移{f[i] = min(f[i],f[j] + (c[i] - c[j ]) * i - s[i] + s[j ]);}}for(int i = te; i < te + m; i ++)ans = min(ans, f[i]);cout << ans ;}

總結

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

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