题目链接
思路:差分,但是由于数据很大所以需要使用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(); } }
c/c++开发分享D – Snuke Prime(大数差分)地址:https://blog.csdn.net/qq_45141428/article/details/112536773
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/596159.html