图片说明
图片说明



题意及思路

  • 题意：h次请求，每次请求在b到e这段路上种t颗数，在满足所有的请求后，循环最少需要种多少颗数。
  • 思路：贪心做法。😂第一步，将得到的请求数组排序（按e，结尾位置从大到小排序）。🙄第二步，对于每一次
请求，😉从请求头到请求尾逐次访问数组q（q是一个存储当前路段是否种树的标记数组，比如q[x]表示路段x是否种过树），如果已经种树（q[x] = 1），则当前请求已种树个数tree++；😊若一次遍历后，tree不满足其请求树数目，则从尾到头逆序种树（置q[x] = 1），🤗同时tree++、ans++。😏详情见代码。

思维图


代码 

#include<bits/stdc++.h>

using namespace std;

const int M = 5005,N = 3e4+5;
int q[N] = {0};

struct T{
	int b,e,t;
}querry[M];

bool cmp(T t1,T t2){
	return t1.e < t2.e;
}

int main(){
	std::ios::sync_with_stdio(false);
    cin.tie(0);
    int n,h;
    cin >> n >> h;
    for(int i=1;i<=h;i++){
    	cin >> querry[i].b >> querry[i].e >>querry[i].t;
	}
	
	sort(querry+1,querry+1+h,cmp);
	
	int ans = 0;
	for(int i=1;i<=h;i++){
		int tree = 0;
		for(int j=querry[i].b;j<=querry[i].e;j++){
			if(q[j]==1) tree++;
		}
		if(tree<querry[i].t){
			for(int j=querry[i].e;j>=querry[i].b;j--){
				if(tree==querry[i].t) break;
				if(q[j]==0){
					tree++;
					ans++;
					q[j] = 1;
				}
			}
		}
	}
	
	cout << ans << endl;
    return 0;
}