P1250 种树【洛谷算法习题】
P1250 种树网页链接P1250 种树题目背景一条街的一边有几座房子因为环保原因居民想要在路边种些树。题目描述路边的地区被分割成块并被编号成1 , 2 , … , n 1, 2, \ldots,n1,2,…,n。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民都想在门前种些树并指定了三个号码b bbe eet tt。这三个数表示该居民想在地区b bb和e ee之间包括b bb和e ee种至少t tt棵树。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。输入格式输入的第一行是一个整数代表区域的个数n nn。输入的第二行是一个整数代表房子个数h hh。第3 33到第( h 2 ) (h 2)(h2)行每行三个整数第( i 2 ) (i 2)(i2)行的整数依次为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输入 #19 4 1 4 2 4 6 2 8 9 2 3 5 2输出 #15说明/提示数据规模与约定对于100 % 100\%100%的数据保证1 ≤ n ≤ 3 × 10 4 1 \leq n \leq 3 \times 10^41≤n≤3×1041 ≤ 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≤n1 ≤ t i ≤ e i − b i 1 1 \leq t_i \leq e_i - b_i 11≤ti≤ei−bi1。解题思路本题核心是贪心算法求解满足所有区间种树约束的最小树木数量。为了让种的树尽可能被多个区间复用采用最优贪心策略将所有居民的种树要求按区间右端点升序排序优先处理右端点更小的区间处理每个区间时先统计已种植的树木数量若不满足要求则从区间右端点向左补种。这种补种方式能让树木覆盖更多后续的区间最大化复用效率从而保证总种树数量最少。算法逻辑简单直观时间复杂度完全适配题目给定的数据规模最终得到全局最优解。总结核心逻辑贪心优先处理右端点靠左的区间从右往左补种树木最大化复用率。关键操作区间按右端点排序、统计区间内已种树木、逆向补种满足约束。效率保障贪心策略保证结果最优无复杂计算高效处理所有测试用例。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;structline{ll s,e,v;}a[5005];ll n,m,ans0;boolused[30005]{0};boolcmp(line x,line y){returnx.ey.e;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld%lld,n,m);for(ll i1;im;i)scanf(%lld%lld%lld,a[i].s,a[i].e,a[i].v);sort(a1,a1m,cmp);for(ll i1;im;i){ll k0;for(ll ja[i].s;ja[i].e;j)if(used[j])k;if(ka[i].v)continue;for(ll ja[i].e;ja[i].s;j--){if(!used[j]){used[j]1;k;ans;if(ka[i].v)break;}}}printf(%lld,ans);return0;}
)
