(未完待续)简单的 贪心 入门。
题目链接:LibreOJ 10001。
题目
题目描述
某条街被划为 $n$ 条路段,这 $n$ 条路段依次编号为 $1,2,\cdots,n$。每个路段最多可以种一棵树。现在居民们给出了 $h$ 组建议,每组建议包含三个整数 $b,e,t$,表示居民希望在路段 $b$ 到 $e$ 之间至少要种 $t$ 棵树。这些建议所给路段的区间可以交叉。请问:如果要满足所有居民的建议,至少要种多少棵树。
题解
思路
显然是贪心。排序以后求解即可。
代码
#include<cstdio>
#include<algorithm>
using std::sort;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
register char ch=getchar();
register int res=0;
while(ch<'0'||'9'<ch)ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return res;
}
const int MAXN=30000+5;
const int MAXH=5000+5;
struct Node{
int b,e,t;
void Read(void){
b=read(),e=read(),t=read();
//scanf("%d%d%d",&b,&e,&t);
return;
}
bool operator<(const Node &a)const{
return e<a.e;
}
};
bool vis[MAXN];
int n,h;
Node I[MAXH];
int main(void){
register int i,j,sum;
n=read(),h=read();
//scanf("%d%d",&n,&h);
for(i=1;i<=h;++i)
I[i].Read();
sort(I+1,I+h+1);
for(i=1;i<=h;++i){
sum=0;
for(j=I[i].b;j<=I[i].e;++j)
sum+=(int)vis[j];
if(sum<I[i].t){
sum-=I[i].t;
for(j=I[i].e;j>=I[i].b;--j){
if(!vis[j]){
vis[j]=true;
++sum;
if(!sum)
break;
}
}
}
}
sum=0;
for(i=1;i<=n;++i)
sum+=(int)vis[i];
printf("%d\n",sum);
return 0;
}
Thanks for sharing your thoughts about Gabriel. Regards