自动搬运

查看原文

来自洛谷，原作者为

	gdf_yhm 智者搭桥，愚者筑墙。

搬运于2025-08-24 21:51:42，当前版本为作者最后更新于2022-11-15 14:38:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P3697

前言

一道学校比赛的题，弄发双倍经验。

赛时想到是贪心，写一半发现写不下去。细节挺多。

另，后来发现的，AT_joi2017ho_b，注意加换行。

思路

贪心。

首先，不加快车时，能到达的车站应跟在特急车停的站之后。即对于 $s_i$ 和 $s_{i+1}$ 之间的 $j$，如果 $j$ 可以到达，从 $s_i$ 到 $j$ 的站都符合条件。

再考虑快车。

对于一个站，最快的到达方式是：先坐特急车到最近的站点，再坐快车到最近的站点，最后转慢车。这样 $m$ 个特急车停靠的站点将整条线路分成 $m-1$ 段，分别处理。

在一段之内，从 $s_i$ 出发只坐慢车最远可以到 $pos_1$,自身贡献 $pos_1-s_i+1$ 个站。如果要在这一段增设快车站，最优是设在 $pos_1+1$ 处，最远能到 $pos_2$，贡献 $res_2$ 是 $pos_2-pos_1$。以此类推。直到有 $pos_k \ge s_{i+1}$ 为止。

这样，每段会有一定数量的可以设快车站的点，分别有一定贡献。用优先队列，选出前 $k$ 大贡献即可。

实现

思路好想，实现难些。

注意：

• 在 $i$ 到 $j$ 之间有 $j-i+1$ 个点，$j-i$ 个间隔。
• $1$ 号点不算，终点单独算。
• 快车站包含特快车站，$k$ 要先减 $m$。

于是就写了一发：

int n,m,k,a,b,c,t;
int pos,res,flag,ans;
int s[maxn];
priority_queue <int> q;

signed main(){
	scanf("%lld%lld%lld",&n,&m,&k);
	k-=m;
	scanf("%lld%lld%lld%lld",&a,&b,&c,&t);
	for(int i=1;i<=m;i++)scanf("%lld",&s[i]);
	for(int i=1;i<m;i++){
		pos=s[i];flag=0;
		while(pos<s[i+1]){
			if(t-(s[i]-1)*b-(pos-s[i])*c<0)break;
			res=(t-(s[i]-1)*b-(pos-s[i])*c)/a+1;
			if(pos+res>=s[i+1]){
				res=s[i+1]-pos;
				pos=s[i+1];
			}
			pos+=res;
			if(!flag){
				ans+=res;
				flag=1;
			}
			else	q.push(res);
		}
	}
	if(t>=(n-1)*b)ans++;
	while(!q.empty() && k){
		k--;
		ans+=q.top();
		q.pop();
	}
	printf("%lld",ans-1);
}

80分。MLE。

一组数据：

1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000

在这里，会找出 $1000000000$ 个贡献为 $1$ 的点并入队。显然，后面是不需要那么多的。

又可以发现，在 每一段中，设置车站的贡献单调不增。所以，对于每一段，只需要入队前 $k$ 个贡献。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=30010;

int n,m,k,a,b,c,t;
int pos,res,cnt,ans;
int s[maxn];
priority_queue <int> q;

signed main(){
	scanf("%lld%d%d",&n,&m,&k);
	k-=m;
	scanf("%lld%lld%lld%lld",&a,&b,&c,&t);
	for(int i=1;i<=m;i++)scanf("%lld",&s[i]);
	for(int i=1;i<m;i++){
//		cout<<i<<" "<<s[i]<<endl;
		pos=s[i];cnt=0;
		while(pos<s[i+1]){
			++cnt;
			if(t-(s[i]-1)*b-(pos-s[i])*c<0)break;
			res=(t-(s[i]-1)*b-(pos-s[i])*c)/a+1;
			if(pos+res>=s[i+1]){
				res=s[i+1]-pos;
				pos=s[i+1];
			}
			pos+=res;
			if(cnt==1){
				ans+=res;
//				cout<<ans<<endl;
			}
			else{
				q.push(res);
//				cout<<res<<endl;	
			}
			if(cnt>k+1)break;
//			cout<<res<<" "<<pos<<endl;
		}
	}
	if(t>=(n-1)*b)ans++;
//	cout<<ans<<endl;
	while(!q.empty() && k){
		k--;
		ans+=q.top();
		q.pop();
//		cout<<ans<<endl;
	}
	printf("%lld",ans-1);
}