[NOIP2020-test2]公交车

【题目描述】

U142335 公交车

\(\text{LYK}\) 在玩一个游戏。

有 \(k\) 群小怪兽想乘坐公交车。第 \(i\) 群小怪兽想从 \(xi\) 出发乘坐公交车到 \(yi\)。但公交车的容量只有 \(M\),而且这辆公交车只会从 \(1\) 号点行驶到 \(n\) 号点。

\(\text{LYK}\) 想让小怪兽们尽可能的到达自己想去的地方。它想知道最多能满足多少小怪兽的要求。

当然一群小怪兽没必要一起上下车,它们是可以被分开来的。

对于 \(30\) % 的数据小怪兽的总数不超过 \(10\) 只,\(n≤10\)。

对于 \(60\) % 的数据 \(k,n≤1000\)。

对于 \(100\) % 的数据 \(1≤n≤20000\),\(1≤k≤50000\),\(1≤M≤100\),\(1≤ci≤100\),\(1≤xi<yi≤n\)


【解题思路】

对于 \(k≤50000\) 的数据范围, \(O(n^2)\) 的DP是可行的。但很遗憾,我并不会DP,所以选择贪心。

将公交车行驶的路线看作整体区间,小怪兽想从 \(xi\) 走到 \(yi\) 就可以抽象为区间 \([1,n]\) 的子区间 \([xi,yi]\) ,这样,我们将这道题目转化为了经典的贪心模型:“活动安排“。

如果对这一模型也没有印象,可以尝试一下这道题目:T142557 [SDFZ-test-01]活动安排 Act

贪心策略

第 \(i\) 群小怪兽想从 \(xi\) 出发乘坐公交车到 \(yi\) ,我们将这样的位置改变称为一次移动,\(xi\) 是始发站, \(yi\) 是终到站。

我们对所有的移动进行按终到站从小到大排序,这样使得每一次移动尽量靠近整个区间的左端,而终到站相同,我们按始发站从大到小排序,这样使得选中的每一次移动都尽量靠近整个区间的右端,这样,每一次移动的区间长度都会最小,从而得到整体最优解。

选择第一次移动作为初始移动,遍历剩下的排完序的每一次移动,当下一次移动的起始时间大于等于前一个移动的终到站时,小怪物们就可以到达,否则不能。

容量限制

为了避免公交车挤上去超过 \(M\) 只小怪物,沦为一列印度火车,我们需要维护一个数组 \(f\) 来记录在第 \(i\) 站时,车上有多少只小怪物

假设现在我们已经取出了一次移动 \([l,r]\) ,只需要从 \(l\) 到 \(r\) 遍历 \(f\) 数组,求出最大值以及最小残余容量 \((M-MAX)\) ,就能得到 \(T=\min(w,(M-MAX))\) 。——这里的T表示,在当前移动中,实际上有多少小怪物能上车。

代码如下:

for(int i = l; i < r; ++i) MAX = max(MAX,f[i]);
T = min(w,M - MAX);
for(int i = l; i < r; ++i) f[i] += T;

凭借这个简单的贪心,我们能够获得 60 分的好成绩。

线段树优化

在上文给出的代码中,时间复杂度的瓶颈在于两点:区间最大值和区间加法。显然,我们可以用线段树做一个卓有成效的优化,将时间复杂度降低至 \(O(klogn)\) 。

线段树需要记录区间max值,具体不作赘述,详见AC代码。


代码(60 pts & 100 pts)

//贪心,60 pts

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long ll;

struct Seg
{
	int l,r,w;
	bool operator <(const Seg &a)const {return r < a.r;}
};

Seg s[50010]; 
int f[50010];//每一时刻 bus 上的人数  

int main()
{
	int k,n,M;ll ans = 0;
	scanf("%d%d%d",&k,&n,&M);
	
	for(int i = 1; i <= k; ++i) scanf("%d%d%d",&s[i].l,&s[i].r,&s[i].w);
	sort(s+1,s+n+1);//按右端点排序 
	
	int now = 0;
	for(int x = 1; x <= n; ++x)
	{
		int MAX = 0,MIN = 0; 
		int l = s[x].l,r = s[x].r,w = s[x].w;
		
		now = l;
		for(int i = l; i < r; ++i) MAX = max(MAX,f[i]);
		MIN = min(w,M - MAX);
		for(int i = l; i < r; ++i) f[i] += MIN;
		ans += MIN;			
	}
	
	printf("%lld\n",ans);
	return 0;
}

//线段树优化贪心, 100pts

#include<iostream>
#include<cstdio>
#include<algorithm>
#define reg register 
using namespace std;

const int N = 50000 + 10;
typedef long long ll;

struct Seg{int l,r,w;};

bool cmp(Seg a,Seg b)
{
	if(a.r != b.r) return a.r < b.r;
	else return a.l > b.l;//按右端点排,相同的比较长短 
}

struct SegmentTree{int l,r,maxx,tag;};

#define ls p<<1
#define rs p<<1|1
#define mid ((t[p].l+t[p].r)>>1)

SegmentTree t[N << 2];
Seg s[N];   

void refresh(int p){t[p].maxx = max(t[ls].maxx,t[rs].maxx);}

void build(int p,int l,int r)
{
	t[p].l = l,t[p].r = r,t[p].maxx = 0,t[p].tag = 0;
	if(l == r) return;
	build(ls,l,mid);
	build(rs,mid + 1,r);
	refresh(p);
}

void pushup(int p,int v)
{
	t[p].maxx = t[p].maxx + v;
	t[p].tag = t[p].tag + v; 
}

void pushdown(int p)
{
	if(!t[p].tag) return;
	pushup(ls,t[p].tag);
	pushup(rs,t[p].tag);
	t[p].tag = 0;
}

void update(int p,int l,int r,int v)
{
	if(l <= t[p].l && t[p].r <= r) return pushup(p,v);
	pushdown(p);
	if(l <= mid) update(ls,l,r,v);
	if(r > mid) update(rs,l,r,v);
	refresh(p);
}

inline int query(int p,int l,int r)
{
	if(l <= t[p].l && t[p].r <= r) return t[p].maxx;
	pushdown(p);
	int res = 0;
	if(l <= mid) res = max(res,query(ls,l,r));
	if(r > mid) res = max(res,query(rs,l,r));
	return res;
}

int main()
{
	int k,n,M,ans = 0;
	scanf("%d%d%d",&k,&n,&M);
	
	for(reg int i = 1; i <= k; ++i) scanf("%d%d%d",&s[i].l,&s[i].r,&s[i].w);
	sort(s+1,s+k+1,cmp);//按右端点排序 
	
	build(1,1,n);//建树 
	
	int now = 0;
	for(reg int i = 1; i <= k; ++i)//切记不要把 k 写成 n ! 
	{
		reg int MAX = 0,MIN = 0; 
		reg int l = s[i].l,r = s[i].r,w = s[i].w;
		
		MAX = query(1,l,r-1);//注意是[l,r-1]
		MIN = min(w,M - MAX);
		update(1,l,r-1,MIN);
		ans = ans + MIN;			
	}
	
	printf("%d\n",ans);
	return 0;
}

THE END

上一篇:switch两种写法对比


下一篇:python 模块