专栏文章

【1】题解：P1315 [NOIP 2011 提高组] 观光公交【贪心】

EExFish
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimzt826
此快照首次捕获于
2025/12/01 18:14
3 个月前
此快照最后确认于
2025/12/01 18:14
3 个月前
查看原文
练习贪心中。首先你发现一辆车一定要等齐站点内所有人再出发。然后你考虑到加速的限度：不能让车等人。这样就可以预处理出一个站点的人数（ss），一个站点最后人什么时候到（ww） 这两个信息。然后考虑一段区间的情况。显然预处理出当前 dd 下的到站时间 ll。然后我们考虑如何使用加速器。我们考虑一些乘客是一定要等的，也就是前面延误了后面就要等，这样的情况可以计算出贡献。考虑计算一个区间加速后能少的总时间 pp（也就是 l>wl>w，延误）这样可以简单合并区间，然后求出加速。之后找到最大优化位置直接暴力做就可以了，时间复杂度 O(nk)\mathcal O(nk)。
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,k,d[N],t[N],a[N],b[N];
int l[N],s[N],w[N],p[N],ans;
void utime(){ for(int i=1;i<=n;i++) l[i]=max(l[i-1],w[i-1])+d[i-1]; }
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<n;i++) cin>>d[i];
	for(int i=1;i<=m;i++) cin>>t[i]>>a[i]>>b[i];
	for(int i=1;i<=m;i++)
		s[b[i]]++, w[a[i]]=max(w[a[i]],t[i]);	
	utime();
	for(int j=1;j<=k;j++){
		for(int i=n;i-1;i--){
			p[i-1]=s[i];
			if(l[i]>w[i]) p[i-1]+=p[i];
		}
		int u=0;
		for(int i=1;i<=n;i++)
			if(d[i]&&p[i]>p[u]) u=i;
		d[u]--;
		utime();
	}
	for(int i=1;i<=m;i++) ans+=l[b[i]]-t[i];
	cout<<ans;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...