聊城菜鸟网站建设公司,互联网公司上市,wordpress 备份插件,ps教程自学网【题目描述】一条街道的一边有几座房子。因为环保原因居民想要在路边种些树#xff0c;路边的地区被分割成n块#xff0c;并被编号为1~n。每块大小为一个单位尺寸且最多可总一棵树。每个居民想在门前种些树并制定了三个数b,e,t#xff0c;这三个数代表居民想在b和e之间最少种…【题目描述】一条街道的一边有几座房子。因为环保原因居民想要在路边种些树路边的地区被分割成n块并被编号为1~n。每块大小为一个单位尺寸且最多可总一棵树。每个居民想在门前种些树并制定了三个数b,e,t这三个数代表居民想在b和e之间最少种t棵树当然be,te-b1允许居民想种树的子区域可以交叉由于资金短缺的原因环保部门想请你求出能够满足所有居民的种树要求的书的最少数量。 【输入格式】 第一行为n表示区域的个数第二行为m表示房子的数目接下来m行描述居民的需要 (0be30000,te-b1) 【输出格式】输出一个数表示满足居民的要求所需要种树的最小数量 贪心策略将房子按结束坐标进行排序后从前往后尽可能地将树栽到每个区间的末尾尽可能让后面的房子共用 代码
#includeiostream
#includecstdio
#includecstring
#includealgorithm
using namespace std;int n,m,k,ans;
struct node
{int b,e,t;
}a[5005];
bool used[30005];bool cmp(const node a,const node b)
{return a.eb.e;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnm;for(int i0;im;i){cina[i].ba[i].ea[i].t;}sort(a,am,cmp);memset(used,0,sizeof(used));ans0;for(int i0;im;i){k0;for(int ja[i].b;ja[i].e;j){if(used[j]) k;}if(ka[i].t)continue;ka[i].t-k;for(int ja[i].e;ja[i].b;j--){if(used[j]false){used[j]true;ans;k--;}if(k0)break;}}coutans;return 0;
}同理按照房子的起始位置开始排序也是可以的 代码
#includeiostream
#includecstdio
#includecstring
#includealgorithm
using namespace std;int n,m,k,ans;
struct node
{int b,e,t;
}a[5005];
bool used[30005];bool cmp(const node a,const node b)
{return a.bb.b;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnm;for(int i0;im;i){cina[i].ba[i].ea[i].t;}sort(a,am,cmp);memset(used,0,sizeof(used));ans0;for(int im-1;i0;i--){k0;for(int ja[i].b;ja[i].e;j){if(used[j]) k;}if(ka[i].t)continue;ka[i].t-k;for(int ja[i].b;ja[i].e;j){if(used[j]false){used[j]true;ans;k--;}if(k0)break;}}coutans;return 0;
}
