摆渡车
摆渡车
https://ac.nowcoder.com/acm/problem/21471
题意
安排摆渡车出发的时间，使这些同学的等车时间之和最小。分析
一
根据题意我们就有如下转移式子，令 $f_i$ 是以时间点 $i$ 为结尾的最小等车时间。那么 $$f_i = \min_{j\le i-m} \lbrace f_j+\sum_{j<t_k\le i} (i-t_k) \rbrace$$
这样的时间复杂度为 $O(t^3)$ 必须优化。二
考虑前缀和优化，令 $sum_i$ 为从 $1$ 到 $i$ 的总时间是多少， $cnt_i$ 为从 $1$ 到 $i$ 有多少个人，那么转移方程优化为$$f_i = \min_{j\le i-m}\lbrace f_j+(cnt_i-cnt_j)\times i+sum_j-sum_i \rbrace$$
这样时间复杂度为 $O(t^2)$ 。还是要考虑优化。
三
考虑到 $cnt_i,sum_i$ 都是常数项，考虑斜率优化 $dp$ 。令 $j<i$ 。现在考虑 $i$ 的转移，如果决策点 $j$ 是 $i$ 的最优决策点，则有$$f_i = f_j+(cnt_i-cnt_j)\times i+sum_j-sum_i $$
$$cnt_j\times i+f_i+sum_i-cnt_i\times i = f_j$$
发现，如果要让 $f_i$ 最小，那么就要使该一次函数的截距最小。那么维护一个下凸壳，就可以了。那么如果 $k,j$ 是 $i$ 的决策点，化简之后得到下式。
$$\frac{f_j+sum_j-f_k-sum_k}{cnt_j-cnt_k}\le i(k<j)$$
这样及时从单调队列中弹出不可能成为最优解的队首就可以保证数据的正确了。因为一个数只会加入和弹出队列一次，所以时间复杂度为 $O(t)$ 。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e7+100;
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch=='-')f=1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f?-x:x;
}
int cnt[N],sum[N],n,m,f[N];
int Q[N],l,r,Max;
double K(int y,int x) {
if(cnt[x] == cnt[y]) return 1e9*((f[x]+sum[x]-f[y]-sum[y]));
else return (double) (f[x]+sum[x]-f[y]-sum[y])/(cnt[x] - cnt[y]);
}
int main()
{
n = read();m = read();
for(int i = 1;i <= n;i++) {
int x = read();Max = max(Max,x);
cnt[x]++;sum[x] += x;
}
for(int i = 1;i < Max + m;i++) cnt[i] += cnt[i-1],sum[i] += sum[i-1];
l = 1;r = 0;
for(int i = 0;i < Max + m;i++){
if(i - m >= 0) {
while(l < r && K(Q[r-1],Q[r]) - K(Q[r],i-m) >= 0) r--;
Q[++r] = i - m;
}
while(l < r && K(Q[l],Q[l+1]) - i <= 0) l++;
f[i] = cnt[i] * i - sum[i];
if(l <= r) f[i] = min(f[i],f[Q[l]]+(cnt[i]-cnt[Q[l]])*i-sum[i]+sum[Q[l]]);
}
int ans = 0x3f3f3f3f;
for(int i = Max;i < Max + m;i++) ans = min(ans,f[i]);
cout << ans << endl;
return 0;
} 
今天一面都没问我八股和手写，就问了十几分钟项目，说我项目比较简单，是不是挂了
查看13道真题和解析
