当前位置：首页 > news >正文

[NOIP 2018 普及组] 摆渡车 / [蓝桥杯青少年组国赛 2023] 月球疏散行动

news 2026/5/12 17:15:47

[NOIP 2018 普及组] 摆渡车 / [蓝桥杯青少年组国赛 2023] 月球疏散行动

~~不难发现，这两题一模一样，数据范围，输入输出，代码可以直接复制提交~~
摆渡车知名一点，我就用他来讲了，思路都是一摸一样的

正文

提供一个好理解的O(n∗m)O(n * m)O(n∗m)的写法~~应该没算错，虽然快不了多少~~

说几个重点吧

1.如果你忘记排序…

2.O(Tm)O(Tm)O(Tm)的写法特别悬，O(n2m)O(n^2m)O(n2m)不缺我这份，但是还是简要讲一下：
· 要用桶的，大小要比T大一点，因为车子可能不是刚好接到最晚来的同学
·应为n十分小，完全可以压缩桶，就比如说前面2t时刻空无一人直接把t[i]改成t[i - 1] + 2m就可以（因为最坏就是，i时刻车子走了，i + 1的同学要在i + m上车，如果隔得太久没有人，车子等哪里就可以，但是dp还要转移）
·前缀和优化的话推式子，对于我来说单独理解pre有点莫名其妙

总等待时间 = (i-t₁)+(i-t₂)+...+(i-t_k) = i+i+...+i（共k个）-(t₁+t₂+...+t_k) = i*k-(t₁+t₂+...+t_k)

pre1就是有多少学生（k就是这个区间里的学生数量）
pre2就是到达时间的总和
这样为什么要前缀和是不是超级明显？

O(nm)O(nm)O(nm)的写法，反而好理解，就是在压缩桶的时候记录偏移量而已，这样就不用for后面的一个一个减了

#include<bits/stdc++.h>usingnamespacestd;constexprintN=5e2+2;constexprintM=4e6+2;intt[N],cnt[M],pre1[M],pre2[M],dp[M];signedmain(){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);intn,m;cin>>n>>m;// if (m == 1) {// cout << 0;// return 0;// }for(inti=1;i<=n;i++){cin>>t[i];t[i]++;}sort(t+1,t+n+1);intdel=0;for(inti=1;i<=n;i++){if((t[i]-del)-t[i-1]>=2*m){intc=(t[i]-del)-t[i-1]-2*m;del+=c;}t[i]-=del;}intT=t[n]+m;for(inti=1;i<=n;i++){cnt[t[i]]++;}for(inti=1;i<=T;i++){pre1[i]=pre1[i-1]+cnt[i];pre2[i]=pre2[i-1]+cnt[i]*i;}intans=INT_MAX;for(inti=1;i<=T;i++){dp[i]=i*pre1[i]-pre2[i];for(intj=i-m;j>=max(0,i-2*m+1);j--){dp[i]=min(dp[i],(pre1[i]-pre1[j])*i-(pre2[i]-pre2[j])+dp[j]);}if(i>=t[n]){ans=min(ans,dp[i]);}}cout<<ans;return0;}