题目链接
思路：差分，但是由于数据很大所以需要使用map
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int arr[N],arr2[N];
#define int long long
map<int,int>mp;
void solve(){
int n,C;
cin>>n>>C;
int a,b,c;
for(int i =0;i<n;i++){
cin>>a>>b>>c;
mp[a] +=c;
mp[b+1]-=c;
}
int ans = 0 ,temp = 0, s =0;
for(auto mm :mp){
ans+= (mm.first-temp)*min(s,C);
temp = mm.first;
s+=mm.second;
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _= 1;
//cin>>_;
while (_--) {
solve();
}
}
本文地址：https://blog.csdn.net/qq_45141428/article/details/112536773
