首页 > 代码库 > 洛谷P1250种树（贪心）
洛谷P1250种树（贪心）
题目描述
一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。
写一个程序完成以下工作：
输入输出格式
输入格式：
第一行包含数据N，区域的个数(0<N≤30000)；
第二行包含H，房子的数目(0<H≤5000)；
下面的H行描述居民们的需要：B E T，0<B≤E≤30000，T≤E-B+1。
输出格式：
输出文件只有一行写有树的数目
输入输出样例
输入样例#1：
941 4 24 6 28 9 23 5 2
输出样例#1：
5
/*首先按右端点从小到大排序从最右边开始种树正解是差分约束，不会！ */#include<cstdio>#include<iostream>using namespace std;int m,n,zh[30001]={0},a[5001],b[5001],sz[5001];void qsort(int s1,int s2) //手写快排 { int mid1=b[(s1+s2)/2]; int i=s1,j=s2,t; while (i<=j) { while (b[i]<mid1) i++; while (b[j]>mid1) j--; if (i<=j) { t=b[i];b[i]=b[j];b[j]=t; t=a[i];a[i]=a[j];a[j]=t; t=sz[i];sz[i]=sz[j];sz[j]=t; i++;j--; } } if (i<s2) qsort(i,s2); if (j>s1) qsort(s1,j);}int main(){ int zs=0,i,j,o; cin>>m; cin>>n; for (i=1;i<=n;i++) cin>>a[i]>>b[i]>>sz[i]; qsort(1,n); for (i=1;i<=n;i++) { int js=0; for (j=b[i];j>=a[i];j--) if (zh[j]==1) js++; //计算区域内种了几棵树。 if (js<sz[i]) //如果不够 { o=sz[i]-js; //求出还要种几棵树。 zs+=o; //累加树的棵数不解释 for (j=b[i];j>=a[i];j--) //从最右边开始种树 if (zh[j]==0) { if (o==0) break;zh[j]=1;o--; //当然注意要在没有树的地方才能种树。 } } } cout<<zs; //最后输出最少种多少棵树 return 0;}
洛谷P1250种树（贪心）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。