自动搬运

查看原文

来自洛谷，原作者为

	大宋宝宝 人送外号宋AK,一名11岁的小学生||支持壶关，壶关条件https://www.luogu.com.cn/paste/88dc6t5s

搬运于2025-08-24 23:02:40，当前版本为作者最后更新于2024-09-16 20:51:53，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

可以贪心的想：如果想要种的瓜最少，一定是让重叠的最多，那么我们就可以将数组按照右端点从小到大排序，然后种树时从后往前枚举，只要这个点之前没有种过瓜，就在这个点种瓜，这样重叠的瓜的数量就最多，也就是种的瓜的数量最少。详见代码注释。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
// ans 表示总数 
bool b[5001];
// b 数组用来标记哪些点种过树了 
struct shu {
	int b,e,t;
} a[5001];
bool cmp(shu a1,shu a2) {
	return a1.e<a2.e;
}
//按照右端点从小到大排序的函数 
int main()
{
	cin>>n>>m;
	for(int i=1; i<=m; i++)	{
		cin>>a[i].b>>a[i].e>>a[i].t;
		//输入 
	}
	sort(a+1,a+m+1,cmp);
	//按照右端点从小到大排序 
	for(int i=1; i<=m; i++)	{
		for(int j=a[i].b; j<=a[i].e; j++) {
			if(b[j]&&a[i].t>0) a[i].t--;
			//如果和之前种的有重合，就让现在要种的次数减一 
			//前提是种的次数不能减到 0 以下了，不然会 RE 
		}
		int now=a[i].e;
		// now 表示当前要种的树的位置 
		while(a[i].t--)	{
			while(b[now]) now--;
			//如果当前位置已经种过树了 
			//就考虑前一个位置 
			//直到当前位置没有种过树为止 
			b[now]=1;
			//在当前位置种一棵树，然后标记此处种了树 
			ans++;
			//总数加一 
		}
	}
	cout<<ans;
	//输出总数 
	return 0;
}

AC记录