企业官网建设流程全解析

小辰的智慧树

时间限制：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 ′ h'h′的树，砍去长度x xx获得智慧x ( 2 h ′ − x ) x(2h' - x)x(2h′−x)。若将砍伐视为多次砍下长度为1 11的单位：
  • 第一次砍时高度为h ′ h'h′，收益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)−1=2h′−3；
  • 第k kk次砍时收益为2 ( h ′ − k + 1 ) − 1 2(h' - k + 1) - 12(h′−k+1)−1。
• 结论：对于任意一棵树，它在高度为i ii时被砍掉1 11单位长度，能提供固定收益2 i − 1 2i - 12i−1，且能砍的高度范围是[ c i + 1 , h i ] [c_i+1,\ 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. 算法实现

1. 差分统计：用一个数组d记录高度i ii处能砍的树的数量。
   对于第i ii棵树( h , c ) (h, c)(h,c)，它能砍的高度区间是[ c + 1 , h ] [c+1, h][c+1,h]，我们在差分数组上d[h]++，d[c]--。
   之后从高到低遍历高度，d[i] += d[i+1]，此时d[i]即表示在高度i ii处可砍的单位总数。
2. 贪心选取：从最高高度（10 6 10^6106）向下遍历：
   • 若d[i] <= m，则全部砍掉，智慧累加(2*i - 1) * d[i]，剩余长度m -= d[i]；
   • 否则，只能砍m个单位，智慧累加(2*i - 1) * m，m归零并结束。
3. 输出：最终的累加和即为最大智慧。

3. 复杂度分析

• 时间复杂度：O ( n + max ⁡ h ) O(n + \max h)O(n+maxh)，n ≤ 10 6 n \le 10^6n≤106，max ⁡ h ≤ 10 6 \max h \le 10^6maxh≤106，完全可行。
• 空间复杂度：O ( max ⁡ h ) O(\max h)O(maxh)的差分数组。

总结

将每次砍伐的收益按照砍伐时的高度拆分成独立单位，利用差分数组快速统计每个高度上的可砍次数，再按高度从高到低贪心选取，保证了在长度限制下的总收益最大。整个过程避免了复杂的动态规划，简洁高效。

代码简要说明

1. 读入与差分：d数组初始全0 00。对每棵树(h, c)，执行d[h]++与d[c]--。
2. 后缀和还原：从10 6 10^6106向下遍历，d[i] += d[i+1]得到高度i ii处的单位数。
3. 贪心累加：同样从高向低遍历，对每个高度i ii，若d[i] <= m则全取，否则取剩余m个。累加智慧并更新m。
4. 输出结果：cout << sum。

代码内容

#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;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;ll m;cin>>n>>m;vector<ll>d(1000005);for(ll i=1;i<=n;i++){ll h,c;cin>>h>>c;d[h]++;d[c]--;}ll sum=0;for(ll i=1000000;i>=0;i--){d[i]+=d[i+1];if(d[i]<=m){sum+=(2*i-1)*d[i];m-=d[i];}else{sum+=(2*i-1)*m;m=0;break;}}cout<<sum<<"\n";return0;}