果然蒟蒻只會普及組的題…… $——By\mathcal{C}halotto$

---

題目描述

有 $n$ 名同學要乘坐擺渡車從人大附中前往人民大學，第 $i$ 位同學在第 $t_i$ 分鐘去等車。只有一輛擺渡車在工作，擺渡車容量可以視為無限大。擺渡車從人大附中出發、把車上的同學送到人民大學、再回到人大附中（去接其他同學），這樣往返一趟總共花費 $m$ 分鐘（同學上下車時間忽略不計）。擺渡車要將所有同學都送到人民大學。

凱凱很好奇，如果他能任意安排擺渡車出發的時間，那么這些同學的等車時間之和最小為多少呢？

注意：擺渡車回到人大附中后即刻出發。

---

輸入格式

第一行包含兩個正整數 $n,m$ ，以一個空格分開，分別代表等車人數和擺渡車往返一趟的時間。

第二行包含 $n$ 個正整數，相鄰兩數之間以一個空格分隔，第 $i$ 個非負整數 $t_i$ 代表第 $i$ 個同學到達車站的時刻。

---

輸出格式

輸出一行，一個整數，表示所有同學等車時間之和的最小值（單位：分鐘）。

---

樣例輸入1

5 1
3 4 4 3 5

樣例輸出1

0

樣例說明

同學 $1$ 和同學 $4$ 在第 $3$ 分鐘開始等車，等待 $0$ 分鐘，在第 $3$ 分鐘乘坐擺渡車出發。擺渡車在第 $4$ 分鐘回答人大附中。

同學 $2$ 和同學 $3$ 在第 $4$ 分鐘開始等車，等待 $0$ 分鐘，在第 $4$ 分鐘乘坐擺渡車出發。擺渡車在第 $5$ 分鐘回到人大附中。

同學 $5$ 在第 $5$ 分鐘開始等車，等待 $0$ 分鐘，在第 $5$ 分鐘乘坐擺渡車出發。自此所有同學都被送到人民大學。總等待時間為 $0$ 。

---

樣例輸入2

5 5
11 13 1 5 5

樣例輸出2

4

樣例說明

同學 $3$ 在第 $1$ 分鐘開始等車，等待 $0$ 分鐘，在第 $1$ 分鐘乘坐擺渡車出發。擺渡車在第 $6$ 分鐘回答人大附中。

同學 $4$ 和同學 $5$ 在第 $5$ 分鐘開始等車，等待 $1$ 分鐘，在第 $6$ 分鐘乘坐擺渡車出發。擺渡車在第 $11$ 分鐘回到人大附中。

同學 $1$ 在第 $11$ 分鐘開始等車，等待 $2$ 分鐘；同學 $2$ 在第 $13$ 分鐘開始等車，等待 $0$ 分鐘。他/她們在第 $13$ 分鐘乘坐擺渡車出發。自此所有同學都被送到人民大學。總等待時間為 $4$ 。可以證明，沒有總等待時間小于 $4$ 的方案。

---

數據規模與約定

對于 $10\%$ 的數據， $n\le 10,m=1,0\le t_i\le 100$ 。
對于 $30\%$ 的數據， $n\le 20,m\le 2,0\le t_i\le 100$ 。
對于 $50\%$ 的數據， $n\le 500,m\le 100,0\le t_i\le 10^4$ 。
另有 $20\%$ 的數據， $n\le 500,m\le 10,0\le t_i\le 4\times 10^6$ 。
對于 $100\%$ 的數據， $n\le 500,m\le 100,0\le t_i\le 4\times 10^6$ 。

---

?解析?

顯然證明法就是根據題目的意思進行直覺性判斷，從而證明結論成立。

顯然，這是一道 $DP$ 題。
于是設 $f[i]$ 表示第 $i$ 分鐘發出一輛車所要的最小時間，設 $t$ 為最后一個人到達車站的時間。

得到狀態轉移方程：$$f[i]=min\{f[k]+\sum _{k<a[j]\le i}i?a[j]\}(0\le k\le i?m)$$其中 $k$ 表示上一輛末班車回來的時間。

那么最后的答案即為：$ans=min\{f[i]\}(t\le i<t+m)$
$i<t+m$ 是因為最后一個人等的時間不會超過 $m$ 分鐘，不然他可以直接乘之前的一輛走，肯定不是最優解。

時間復雜度： $\Theta (t^{2}n)$

優化

1、前綴和優化

令 $cnt[i]$ 表示到 $i$ 為止到達車站的人數和
$sum[i]$ 表示到 $i$ 為止到達車站的人的時間總和
顯然有：$$\sum _{k<a[j]\le i}i?a[j]=i?(cnt[i]?cnt[k])?(sum[i]?sum[k])$$即，總等待時間 $=$ $i\times (i～k$ 內總人數$)$ $?$ 等待時間在 $i～k$ 內所有人的等待時間之和。

附上一張圖幫助理解：

于是方程變為：$$f[i]=min\{f[k]+i?(cnt[i]?cnt[k])?(sum[i]?sum[k])\}(k\le i?m)$$

時間復雜度：$\Theta (t^2)$

2、轉移優化

顯然，沒有一位同學的等待時間會超過 $2m$ 分鐘。

簡單證明：
考慮最壞的情況，在 $k$ 時刻發了一輛車，有個同學在 $k+1$ 時到達車站，那么擺渡車將在 $k+m$ 時返回，考慮到等待其它學生的情況，擺渡車最晚會在 $k+2m?1$ 時發車，否則還不如分別在 $k+m$ 和 $k+2m$ 的時候發出。

所以， $k$ 的范圍就變為： $i?2m<i\le i?m$ 。

時間復雜度： $\Theta (tm)$
完全不用虛了(??????‵)

---

代碼展示

#include<bits/stdc++.h> #define ll long long #define me(x) memset(x,0,sizeof(x)) #define bi(x) memset(x,0x3f,sizeof(x)) #define ud using namespace std ud; const int maxn=1e7+10; int last_time=-9876543,ans=1<<30; int N,M,t[maxn],f[maxn],sum[maxn]={},cnt[maxn]={}; inline long long read() {long long s=0,f=1; char ch; for(;ch<'0' || ch>'9';ch=getchar()) if(ch=='-') f=-1;for(;ch>='0' && ch<='9';ch=getchar()) s=(s<<1)+(s<<3)+ch-'0'; return s*f; } int main() {N=read(),M=read();for(int i=1;i<=N;++i) {t[i]=read();// Find the last person who reach the stationlast_time=max(last_time,t[i]);++cnt[t[i]];//從0到i時間為止到達車站的人數和sum[t[i]]+=t[i];//從0到i時間為止到達車站的人的時間總和}for(int i=1;i<last_time+M;++i){cnt[i]+=cnt[i-1];sum[i]+=sum[i-1];}for(int i=0;i<last_time+M;++i){if(i>=M&&cnt[i-M]==cnt[i]){f[i]=f[i-M]; continue;}f[i]=cnt[i]*i-sum[i];for(int j=max(i-(M<<1)+1,0);j<=i-M;++j)f[i]=min(f[i],f[j]+(cnt[i]-cnt[j])*i-(sum[i]-sum[j]));} for(int i=last_time;i<last_time+M;++i) ans=min(ans,f[i]);printf("%d\n",ans);return 0; }

總結

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

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