自动搬运

查看原文

来自洛谷，原作者为

	Cry_For_theMoon **

搬运于2025-08-24 21:27:02，当前版本为作者最后更新于2020-09-23 18:32:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

  传送门

  典型的"线段树只是工具人"题目

  大佬们竟然都没有怎么证明贪心？蒟蒻水社区分的机会到了

  把 $m$ 个 $s$ 到 $e$ 的奶牛分开看作 $m$ 个 $s$ 到 $e$ 的区间，这样就不用考虑区间的个数问题了。

  设 $F_{i,j}$ 是地点 $i...j$ 所能选择的最大区间数。

  按照区间贪心的套路，先试试右端点排序。我们假设 $a_i$ 是所有在 $i...j$ 这段里的区间中结束最早的那个。假设最优解没有 $a_i$。那么我们对最优解的所有区间的 左端点排序，把此时开始时间最早的区间记作 $a_j$。

• 如果$a_i,a_j$ 不交，一定可以选择 $a_i$，此时不是最优解

• 如果$a_j$ 完全包含 $a_i$，优先选 $a_i$ 显然可以让后面剩下的资源更多，这是因为在原来的方案里 $e_{a_i}...e_{a_j}$ 这一段的空间比优先选择 $a_i$ 少1，那么必然解不会比选择 $a_i$ 更优。

• 否则 $s_{a_i} < s_{a_j},e_{a_i} < e_{a_j}$，此时选择 $a_i$ ，那么 $e_{a_i}... e_{a_j}$ 这段空间就会多1，显然我们可以选择更多的奶牛上车，即至少不会得到更差解。

  综上，$F_i,j$ 的最优解中一定有一个解是包含 结束时间最早的 那个活动的。

  不过这只是在最初的时候如此。考虑那个熟的不能再熟的区间调度问题，我们也不是一鼓作气把排完序以后找到最前面的一口气选择，而是找到第一个和上一个选择兼容的区间。这题稍有改动，我们如果要选择区间 $a_i$，那么必须保证 $s_{a_i}...e_{a_i}$ 这一段里面的任何一个时刻值都是小于 $c$ 的，而我们只需要维护最大值即可。

  最后，题目本身一个区间里是有 $m$ 头奶牛的，通过我们上面的推断，如果选了第 $i$ 个区间，那么尽可能多的先把第 $i$ 个区间的奶牛选上，维护区间最大值 $maxn$，$\min(m_i,c-maxn)$ 就是当前选择能选择的个数。选择完了以后把区间整体加上一个选择个数即可。

  本人本着代码能暴力就暴力的原则交了一发暴力代码上去，结果 64 分 TLE 泪目。不过看到"区间加""区间最大值"，这就是一个裸的线段树了。

  与多数线段树的题不同的是，这一题难的不是数据结构，而是贪心的猜测与证明（反正我一开始没想出来），所以题解都没有写证明让我很害怕QwQ

  当然，dalao们做贪心题都是"直觉猜测显然成立"的，只有我这种蒟蒻需要证明。

  献上代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=5e4+10;
int n,k,ans,c;
struct Line{
	int m,l,r;
	bool operator<(const Line& l2)const{
		return r < l2.r;
	}
}line[MAXN];
int zt[MAXN];
int tree[MAXN<<2],tag[MAXN<<2];
inline int lc(int x){return x<<1;}
inline int rc(int x){return lc(x)|1;}
void push_up(int);
void push_down(int);
int query(int,int,int,int,int);
void update(int,int,int,int,int,int);
int main(){
	scanf("%d%d%d",&k,&n,&c);
	for(int i=1;i<=k;i++){
		scanf("%d%d%d",&line[i].l,&line[i].r,&line[i].m);
	}
	sort(line+1,line+1+k);
	for(int i=1;i<=k;i++){
		int l = line[i].l,r = line[i].r,m = line[i].m;
		//max [l,r)
		int maxn = query(1,1,n,l,r-1);
		int chose =((c-maxn) < m)?(c-maxn):m;
		ans += chose;
		//[l,r) += chose
		update(1,1,n,l,r-1,chose);
	}
	cout<<ans;
	return 0;
}
void push_up(int x){
	tree[x] = max(tree[lc(x)],tree[rc(x)]);
}
void push_down(int x){
	//只维护max甚至不需要l,r？
	tree[lc(x)] += tag[x];
	tree[rc(x)] += tag[x];
	tag[lc(x)] += tag[x];
	tag[rc(x)] += tag[x]; 
	tag[x] = 0; 
}
int query(int x,int l,int r,int ql,int qr){
	if(ql <= l && qr >= r){
		return tree[x];
	}
	int mid = (l+r)>>1;
	int ans = 0;
	push_down(x);
	if(ql <= mid){
		ans = max(ans,query(lc(x),l,mid,ql,qr));
	}
	if(qr > mid){
		ans = max(ans,query(rc(x),mid+1,r,ql,qr));
	}
	push_up(x);
	return ans;
}
void update(int x,int l,int r,int ql,int qr,int value){
	if(ql <= l && qr >= r){
		tree[x] += value;
		tag[x] += value;
		return;
	}
	int mid = (l+r)>>1;
	push_down(x);
	if(ql <= mid){
		update(lc(x),l,mid,ql,qr,value);
	}
	if(qr > mid){
		update(rc(x),mid+1,r,ql,qr,value);
	}
	push_up(x);
}

  END