奥赛一本通 1423 种树

1423 种树题目大意给定 $m$ 个范围在 $1 \sim n$ 的区间每个区间都有一个种树数量的最少要求求需要种树的最少数量。知识要点排序、贪心、二分解题思路 1将所有区间按右端点排序统计前面区间种到本区间的树数量不满足要求的则尽可能在区间末尾新种一些树时间复杂度为 $O(m \log m mn)$。参考代码 1#includebits/stdc.husingnamespacestd;structRegion{intb,e,t;}E[5005];boolflag[30005];boolcmp(Region A,Region B){returnA.eB.e;}intmain(){intn,m,ans0;scanf(%d%d,n,m);for(inti0;im;i)scanf(%d%d%d,E[i].b,E[i].e,E[i].t);sort(E,Em,cmp);for(inti0;im;i){intcnt0;//已种树的数量for(intjE[i].b;jE[i].ecntE[i].t;j)if(flag[j])cnt;ansE[i].t-cnt;for(intjE[i].e;cntE[i].t;j--)if(!flag[j])flag[j]1,cnt;}printf(%d\n,ans);return0;}解题思路 2将所有种树的位置维护为若干区间显然这些区间的数量不超过 $m$。统计前面区间种到本区间的树数量时使用二分查找确定当前包含哪些已经种树的位置区间然后利用前缀和即可计算。需要新种树时就是从当前区间末尾开始向前延长遇到上一个已经种树区间就直接合并即可时间复杂度为 $O(m \log m)$。参考代码 2#includebits/stdc.husingnamespacestd;structRegion{intb,e,t;}E[5005],P[5005];// P 记录种树的连续区间, t 值为种树总量的前缀和boolcmp(Region A,Region B){returnA.eB.e;}intmain(){intn,m,ans0,num0;// num 记录种树区间的个数scanf(%d%d,n,m);for(inti0;im;i)scanf(%d%d%d,E[i].b,E[i].e,E[i].t);sort(E,Em,cmp);for(inti0;im;i){intl0,rnum;//二分查找左端点所在区间while(lr){intmid(lr1)/2;if(P[mid].eE[i].b)lmid;elsermid-1;}intcntP[num].t-P[l].t;//统计已种树的数量if(l1numP[l1].bE[i].b)cnt-E[i].b-P[l1].b;if(cntE[i].t)continue;P[num]{E[i].e1,E[i].e1,ans};//创建新的空区间左闭右开ansE[i].t-cnt;while(cntE[i].t){if(P[num].b-P[num-1].eE[i].t-cnt){//合并到上一区间cntP[num].b-P[num-1].e;P[num-1].eP[num].e;num--;}else{//延长最后一个种树区间P[num].b-E[i].t-cnt;break;}}P[num].tans;//最后一个区间的前缀和就是答案}printf(%d\n,ans);return0;}