当前位置：首页 > news >正文

P1250 种树【洛谷算法习题】

news 2026/5/15 21:09:31

P1250 种树

网页链接

P1250 种树

题目背景

一条街的一边有几座房子，因为环保原因居民想要在路边种些树。

题目描述

路边的地区被分割成块，并被编号成1 , 2 , … , n 1, 2, \ldots,n1,2,…,n。每个部分为一个单位尺寸大小并最多可种一棵树。

每个居民都想在门前种些树，并指定了三个号码b bb，e ee，t tt。这三个数表示该居民想在地区b bb和e ee之间（包括b bb和e ee）种至少t tt棵树。

居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。

输入格式

输入的第一行是一个整数，代表区域的个数n nn。

输入的第二行是一个整数，代表房子个数h hh。

第3 33到第( h + 2 ) (h + 2)(h+2)行，每行三个整数，第( i + 2 ) (i + 2)(i+2)行的整数依次为b i , e i , t i b_i, e_i, t_ibi,ei,ti，代表第i ii个居民想在b i b_ibi和e i e_iei之间种至少t i t_iti棵树。

输出格式

输出一行一个整数，代表最少的树木个数。

输入输出样例 #1

输入 #1

9 4 1 4 2 4 6 2 8 9 2 3 5 2

输出 #1

说明/提示

数据规模与约定

对于100 % 100\%100%的数据，保证：

1 ≤ n ≤ 3 × 10 4 1 \leq n \leq 3 \times 10^41≤n≤3×104，1 ≤ h ≤ 5 × 10 3 1 \leq h \leq 5 \times 10^31≤h≤5×103。
1 ≤ b i ≤ e i ≤ n 1 \leq b_i \leq e_i \leq n1≤bi≤ei≤n，1 ≤ t i ≤ e i − b i + 1 1 \leq t_i \leq e_i - b_i + 11≤ti≤ei−bi+1。

解题思路

本题核心是贪心算法，求解满足所有区间种树约束的最小树木数量。为了让种的树尽可能被多个区间复用，采用最优贪心策略：将所有居民的种树要求按区间右端点升序排序，优先处理右端点更小的区间；处理每个区间时，先统计已种植的树木数量，若不满足要求，则从区间右端点向左补种。这种补种方式能让树木覆盖更多后续的区间，最大化复用效率，从而保证总种树数量最少。算法逻辑简单直观，时间复杂度完全适配题目给定的数据规模，最终得到全局最优解。

总结

核心逻辑：贪心优先处理右端点靠左的区间，从右往左补种树木，最大化复用率。
关键操作：区间按右端点排序、统计区间内已种树木、逆向补种满足约束。
效率保障：贪心策略保证结果最优，无复杂计算，高效处理所有测试用例。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;structline{ll s,e,v;}a[5005];ll n,m,ans=0;boolused[30005]={0};boolcmp(line x,line y){returnx.e<y.e;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf("%lld%lld",&n,&m);for(ll i=1;i<=m;i++)scanf("%lld%lld%lld",&a[i].s,&a[i].e,&a[i].v);sort(a+1,a+1+m,cmp);for(ll i=1;i<=m;i++){ll k=0;for(ll j=a[i].s;j<=a[i].e;j++)if(used[j])k++;if(k>=a[i].v)continue;for(ll j=a[i].e;j>=a[i].s;j--){if(!used[j]){used[j]=1;k++;ans++;if(k==a[i].v)break;}}}printf("%lld",ans);return0;}