|
#10001. 「一本通 1.1 例 2」种树(题目链接)
大意：给一些区间，每个区间都需要种一定的树，问最少种多少。(3e4)
区间覆盖贪心问题
自己没想出来细节该如何做，贪心思路到是比较简单，就是要优先在区间重叠的地方种上树。
但其实好有一个关键性的步骤，就是要对区间结尾进行由大到小排序，在一个重叠的区间上还需要尽量的靠右端种。
上面图片中的黑色重叠区间中，叉点就没有对号点优。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+500;
const int man = 5e3+500;
int mp[maxn];
struct node{
int l,r,val;
}e[man];
int n,m;
bool cmp(node a,node b){
return a.r<b.r;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;++i) scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].val);
sort(e,e+m,cmp);
for(int i=0;i<m;++i){
int sum = 0;
for(int j=e[i].l;j<=e[i].r;++j) sum+=mp[j];
for(int j=e[i].r;sum<e[i].val;--j){
if(!mp[j]){
mp[j]=1;
sum++;
}
}
}
int ans = 0;
for(int i=1;i<=n;++i) ans+=mp[i];
printf("%d\n",ans);
return 0;
}
| 
转播
