【题目描述】

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