小辰的智慧树【牛客tracker 每日一题】

小辰的智慧树时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述有n nn棵智慧树第i ii棵智慧树的初始高度为h i h_ihi​当前高度为h i ′ h_i^′hi′​。小辰每次可以砍去某一棵智慧树的长度为x ( 0 ≤ x ) x (0≤x)x(0≤x)的树干小辰获得x × ( h i ′ h i ′ − x ) x×(h_i^′h_i^′−x)x×(hi′​hi′​−x)的智慧而后智慧树的当前高度h i ′ ← h i ′ − x h_i^′←h_i^′−xhi′​←hi′​−x。现在陶陶不想让小辰太聪明于是陶陶便限制第i ii棵智慧树高度不能低于c i c_ici​。同时由于小辰的屋子空间有限不能装下长度之和超过m mm的树干。求小辰最多能获得多少智慧。输入描述第一行两个整数n ( 1 ≤ n ≤ 10 6 ) , m ( 1 ≤ m ≤ 10 12 ) n (1≤n≤10^6),m (1≤m≤10^{12})n(1≤n≤106),m(1≤m≤1012)表示智慧树的数量和小辰屋子的空间大小。接下来n nn行第i ii行两个整数h i , c i ( 0 ≤ c i ≤ h i ≤ 10 6 ) h_i,c_i (0≤c_i≤h_i≤10^6)hi​,ci​(0≤ci​≤hi​≤106)表示第i ii棵智慧树的初始高度和第i ii棵智慧树的最低高度。输出描述一行一个整数表示小辰能获得的最大智慧。示例1输入3 6 10 5 9 2 8 1输出98解题思路本题是差分数组 贪心的经典模型将砍树过程拆分成按高度排序的独立单位操作每次砍伐高度越高收益越大因此从高到低贪心选取即可。1. 问题转化砍伐收益重写对于一棵高度为h ′ hh′的树砍去长度x xx获得智慧x ( 2 h ′ − x ) x(2h - x)x(2h′−x)。若将砍伐视为多次砍下长度为1 11的单位第一次砍时高度为h ′ hh′收益2 h ′ − 1 2h - 12h′−1第二次砍时高度变为h ′ − 1 h-1h′−1收益2 ( h ′ − 1 ) − 1 2 h ′ − 3 2(h-1) - 1 2h - 32(h′−1)−12h′−3第k kk次砍时收益为2 ( h ′ − k 1 ) − 1 2(h - k 1) - 12(h′−k1)−1。结论对于任意一棵树它在高度为i ii时被砍掉1 11单位长度能提供固定收益2 i − 1 2i - 12i−1且能砍的高度范围是[ c i 1 , h i ] [c_i1,\ h_i][ci​1,hi​]内的每一个整数高度。全局视角所有树的全部可砍单位分布在不同的高度上每个高度i ii可能有若干棵树可以提供“从i ii砍到i − 1 i-1i−1”这一刀。总目标是在总砍伐长度≤ m \le m≤m的限制下选择收益总和最大的一批单位。由于收益2 i − 1 2i-12i−1随i ii严格递增贪心策略就是优先砍高度最高的单位。2. 算法实现差分统计用一个数组d记录高度i ii处能砍的树的数量。对于第i ii棵树( h , c ) (h, c)(h,c)它能砍的高度区间是[ c 1 , h ] [c1, h][c1,h]我们在差分数组上d[h]d[c]--。之后从高到低遍历高度d[i] d[i1]此时d[i]即表示在高度i ii处可砍的单位总数。贪心选取从最高高度10 6 10^6106向下遍历若d[i] m则全部砍掉智慧累加(2*i - 1) * d[i]剩余长度m - d[i]否则只能砍m个单位智慧累加(2*i - 1) * mm归零并结束。输出最终的累加和即为最大智慧。3. 复杂度分析时间复杂度O ( n max ⁡ h ) O(n \max h)O(nmaxh)n ≤ 10 6 n \le 10^6n≤106max ⁡ h ≤ 10 6 \max h \le 10^6maxh≤106完全可行。空间复杂度O ( max ⁡ h ) O(\max h)O(maxh)的差分数组。总结将每次砍伐的收益按照砍伐时的高度拆分成独立单位利用差分数组快速统计每个高度上的可砍次数再按高度从高到低贪心选取保证了在长度限制下的总收益最大。整个过程避免了复杂的动态规划简洁高效。代码简要说明读入与差分d数组初始全0 00。对每棵树(h, c)执行d[h]与d[c]--。后缀和还原从10 6 10^6106向下遍历d[i] d[i1]得到高度i ii处的单位数。贪心累加同样从高向低遍历对每个高度i ii若d[i] m则全取否则取剩余m个。累加智慧并更新m。输出结果cout sum。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;ll m;cinnm;vectorlld(1000005);for(ll i1;in;i){ll h,c;cinhc;d[h];d[c]--;}ll sum0;for(ll i1000000;i0;i--){d[i]d[i1];if(d[i]m){sum(2*i-1)*d[i];m-d[i];}else{sum(2*i-1)*m;m0;break;}}coutsum\n;return0;}