题目描述
有N（1<=N<=20,000）个站点的轻轨站，有一个容量为C（1<=C<=100）的列车起点在1号站点，终点在N号站点，有K(K<=50,000)组牛群，每组数量为M_i（1<=M_i<=N），行程起点和终点分别为S_i和E_i（1<=S_i<E_i<=N）
计算最多有多少头牛可以搭乘轻轨。
题目解析
贪心+线段树优化
贪心策略：每次选取结束时间最早的是最优解
证明，看这位dalao的详细的证明
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std
;
int k
,n
,c
,ans
;
struct point
{
int s
,e
,m
;
}a
[50005];
struct tnode
{
int l
,r
,lazy
,w
;
}t
[80005];
bool cmp(point a
,point b
)
{
return a
.e
<b
.e
;
}
void build(int l
,int r
,int x
)
{
t
[x
].l
=l
;t
[x
].r
=r
;t
[x
].w
=c
;
if(l
==r
) return;
int mid
=l
+r
>>1;
build(l
,mid
,x
*2);
build(mid
+1,r
,x
*2+1);
}
void down(int x
)
{
if(t
[x
].lazy
)
{
t
[x
*2].w
+=t
[x
].lazy
;
t
[x
*2+1].w
+=t
[x
].lazy
;
t
[x
*2].lazy
+=t
[x
].lazy
;
t
[x
*2+1].lazy
+=t
[x
].lazy
;
t
[x
].lazy
=0;
}
}
void change(int x
,int l
,int r
,int num
)
{
if(t
[x
].l
==l
&&t
[x
].r
==r
)
{
t
[x
].w
+=num
;
t
[x
].lazy
+=num
;
return;
}
down(x
);
if(t
[x
*2].r
>=r
) change(x
*2,l
,r
,num
);
else if(t
[x
*2+1].l
<=l
) change(x
*2+1,l
,r
,num
);
else change(x
*2,l
,t
[x
*2].r
,num
),change(x
*2+1,t
[x
*2+1].l
,r
,num
);
t
[x
].w
=min(t
[x
*2].w
,t
[x
*2+1].w
);
}
int find(int x
,int l
,int r
)
{
if(t
[x
].l
==l
&&t
[x
].r
==r
) return t
[x
].w
;
down(x
);
if(t
[x
*2].r
>=r
) return find(x
*2,l
,r
);
else if(t
[x
*2+1].l
<=l
) return find(x
*2+1,l
,r
);
else
{
t
[x
].w
=min(t
[x
*2].w
,t
[x
*2+1].w
);
return min(find(x
*2,l
,t
[x
*2].r
),find(x
*2+1,t
[x
*2+1].l
,r
));
}
}
int main()
{
scanf("%d%d%d",&k
,&n
,&c
);
for(int i
=1;i
<=k
;i
++)
scanf("%d%d%d",&a
[i
].s
,&a
[i
].e
,&a
[i
].m
);
sort(a
+1,a
+1+k
,cmp
);
build(1,n
,1);
for(int i
=1;i
<=k
;i
++)
{
int f
=find(1,a
[i
].s
,a
[i
].e
-1);
if(f
)
{
change(1,a
[i
].s
,a
[i
].e
-1,-min(f
,a
[i
].m
));
ans
+=min(f
,a
[i
].m
);
}
}
cout
<<ans
;
}
