登錄—專業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;
}

?