20190709种树（洛谷P1250）

题目描述

一条街道的一边有几座房子，因为环保原因居民想要在路边种些树，路边的居民被分割成 n 块，并被编号为 1…n。每块大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个数b,e,t。这三个数分别表示该居民想在b和e之间最少种t棵树，当然b≤e，t≤e-b+1，允许居民想种树的子区域可以交叉。出于资金紧缺的原因，环保部门请你求出能够满足所有居民的种树要求时所需要种的树的最少数量。 

输入

第一行为 n，表示区域的个数。
第二行为 h，表示房子的数目。
下面 h 行描述居民的需要：b,e,t（0＜b≤e≤30000，t≤e-b+1）分别用一个空格分开。

输出

输出只有一个数，为满足所有居民的建议，所需要种树的最少数量。 

样例输入

9
4
1 4 2
4 6 2
8 9 2
3 5 2

样例输出

5

提示

30% 的数据满足 0<n≤1000，0<h≤500；
100% 的数据满足 0<n≤3×10^4，h≤5000，0<b≤e≤3×10^4 ，t≤e−b+1。

#include<bits/stdc++.h>
using namespace std;
struct X{//结构体
	int b,e,t;
}a[5005];
bool cmp(X x,X y)//这不是问题的关键
{
	if(x.e!=y.e) return x.e<y.e;
	return x.b>y.b;
}
bool xyds[30005];
int main()
{
	int n,h;
	cin>>n>>h;
	for(int i=1;i<=h;i++) cin>>a[i].b>>a[i].e>>a[i].t;
	sort(a,a+h+1,cmp);//结构体排序
	int ans=0;
	for(int i=1;i<=h;i++)
	{
		int B=a[i].b,E=a[i].e,T=a[i].t;
		for(int j=B;j<=E;j++)
		{
			if(xyds[j]) T--;//扣除已种的树
		}
		if(T>0)
		{
			for(int j=E;j>=B;j--)
			{
				if(!xyds[j]) T--,xyds[j]=1,ans++;//在右端种树
				if(!T) break;
			}
		}
	}
	cout<<ans;
	return 0;
}

　　贪心即可解决（俺不会差分约束555）。结构体sort排序即可解决（这不是问题的关键）。思路：首先按照区间的结束位置（b）从小到大排序，若结束位置相同，则按照起始位置（e）从大到小排序（可用sort解决）；然后就优先在区间的尾部种树，数量为总数（t）减去已种数量。另外需要用bool数组标记已种树的位置，防止重复种树。最终输出ans即可。