小辰的智慧树（差分+前缀和）

登录—专业IT笔试面试备考平台_牛客网

1.考虑总长度之和不能超过m，2考虑限制每棵树高度不能低于ci，如果用二分最短输能截到的高度，还要另外去判断，是否每棵树mid都能严格大于ci ，这样容易超时，换个角度，每棵树我能截到的高度是从a到b,而且最优解是每次只截一个单位长度，因此我想要结果越大就要保持我截到的越高越好，差分和前缀和将所有能截到的位置统计起来，并统计了每个位置有几棵树能截，从最高位置遍历，累加总数不超过m即可

#include<bits/stdc++.h>
using namespace std;
//#define int long long
typedef long long ll;
const int N=2e6+10;
#define endl '\n'
ll sum[N],x[N];
int main(){ll n,m;cin>>n>>m;int a,b;for(int i=1;i<=n;i++){cin>>a>>b;x[b+1]++;//(从b+1的高度开始截，截完后树的高度刚好是b即刚好大于等于ci)x[a+1]--;}ll ans=0;sum[0]=x[0];for(int i=1;i<=2e6+10;i++){sum[i]=sum[i-1]+x[i];}for(int i=2e6+10;i>=0;i--){if(sum[i]){ll xx=min(m,sum[i]);m-=xx;ans+=xx*(2*i-1);//(x*(i+i-x)if(m<=0)break;}}cout<<ans<<endl;
}