自动搬运

查看原文

来自洛谷，原作者为

	ran_qwq debug 深入思考 只靠样例与自己！

搬运于2025-08-24 23:10:16，当前版本为作者最后更新于2025-02-27 18:58:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

约定：以下称快车为高速电车，中车为准高速电车，慢车为普通列车。

本人语文不好，读错了两次题：

• 只能从 $i$ 走到 $i+1$，不能反着走。
• 快车和中车都是两个站（不管是否停靠）之间要走 $B$ / $C$ 分钟，不是两个停靠的站之间。

小清新贪心题。

Observation 1：对于每个站，到达它的最优方式永远是先坐快车到前面离它最近的快车站，再坐中车到前面离它最近的中车站，再坐慢车。

Prove 1：因为 $B\le C\le A$ 且换乘不需要时间。

Observation 2：每两个快车站间独立，即在 $i$ 和 $i+1$ 快车站间放置中车站，不会影响 $i+1$ 和 $i+2$ 间点的可达性。

Prove 2：根据 Observation 1，如果需要达到快车站 $i+1$ 和 $i+2$ 之间的点，最优策略是坐快车坐到 $i+1$，坐到 $i$ 再坐中车慢车到 $i+1$ 是不优的。

Observation 3：有一种贪心策略：对于每两个快车站间，从前往后放中车站，每次在第一个无法达到到的点处放置中车站，直到 放了还是无法达到 或 这两个快车站间已经放了 $M-K$ 个位置 为止。

Prove 3：显然我们可以看作从前往后放中车站。设放了 $k$ 个，若放在之前可达的位置，我们可以把它平移到不可达的位置，设平移了 $x$ 步。我们多花了 $Cx$ 分钟，多走了原本花 $Ax$ 时间才能走的路程，肯定更优。若隔空放，隔空的部分不可达而却在坐中车上多花了时间，也是不赚的。

Observation 4：根据 Observation 3，现在我们的问题就是在每两个快车站之间放多少个中车站。我们转化为这么一个问题：设 $v_{i,j}$ 为 $i$ 和 $i+1$ 之间放第 $j$ 个中车站能新增多少个可达点。每个 $v_i$ 可以取一个前缀，一共最多取 $K-M$ 个，最大化取得的总和。

Prove 4：简单的转化，显然。

现在有一个简单的 $O(MK^2)$ 背包，$f_{i,j}$ 为前 $i$ 段取了 $j$ 个的最大值。转移枚举当前取的个数 $k$，这是简单的。

Observation 5：对于一个 $i$，现在的 $v_{i,j}$ 不增。

Prove 5：距离快车站 $i$ 越远，坐中车时间越长，可以预留给坐慢车的时间越短，坐慢车的距离越短，每次拓展的距离越短。

Observation 6：可以把取一个前缀的条件去掉。

Prove 6：根据 Observation 5，$v_{i,j}$ 不增，不取前缀不会比取前缀优。

Observation 7：又可以转化为把 $v_{i,j}$ 排成一行，取 $K$ 个数使总和最大。

Prove 7：不同段之间并没有外加的限制。

现在可以直接排序后取前 $K$ 个了。复杂度 $O(MK\log MK)$。如果用优先队列维护，动态把当前已经不在前 $K$ 个的删去，复杂度 $O(MK\log K)$。

int n,m,k,a,b,c,as=-1,p[N]; ll t;
priority_queue<int,vi,greater<int>> q;
void QwQ() {
	n=rd(),m=rd(),k=rd()-m,a=rd(),b=rd(),c=rd(),t=rdll();
	for(int i=1;i<=m;i++) p[i]=rd();
	for(int i=1;i<=m;i++) {
		if(1ll*(p[i]-1)*b>t) break;
		if(i==m) {as++; break;}
		as+=min((ll)p[i+1]-p[i],(t-1ll*(p[i]-1)*b)/a+1); int ct=0;
		for(ll x=p[i]+(t-1ll*(p[i]-1)*b)/a+1,y=t-1ll*(p[i]-1)*b-(x-p[i])*c,nx;y>=0&&x<p[i+1];y-=(nx-x)*c,x=nx) {
			nx=min((ll)p[i+1],x+y/a+1),q.push(nx-x);
			if(++ct==k) break;
		}
		for(;q.size()>k;) q.pop();
	}
	for(;q.size();) as+=q.top(),q.pop();
	wr(as,"\n");
}