【题目描述】
\(\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;
}