最关键的想法就是每个位置一定用的是当前能用的最便宜的水，因为到后面可能有更便宜的
然后其他还没用上的水我们也留着，假装此时已经买了，但是如果发现后面有更优的再反悔也不迟
每相邻两个朋友之间我们把最便宜的一些水消耗了
然后考虑有朋友来送水了
设这个朋友的水的最大体积为 $mx$，价格为 $cst$，如果系统完全装得下 $mx$ 的水那么 $ ext{我全都要}$ 即可
如果装不下那么看看系统里最贵的那个单位水 $x$，如果价格大于 $cst$ ，那么我们就不要这个 $x$ 了，直接反悔，问就是根本没买过
（有点像网络流里面的反向边...）
那么价格为 $cst$ 的水就可以多一单位了，然后不断重复直到水的价格都小于等于 $cst$ 或者这 $mx$ 单位的水全部加入到系统里面
实际上代码实现的时候并不需要一单位一单位考虑
到了最后可能系统里还剩下一些水，当然也是假装根本没买过就行了（实际上的确没买过 $2333$）
怎么维护的问题自己开心就好了，这里学的官方题解用 $map$ （$map$ 竟然还能这么用）
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<map> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=5e5+7; int Q,n,m,Cap,C0;//Cap是容量 struct dat { int t,mx,cst;//每个朋友到达时间,最大水量,单位价值 dat (int _t=0,int _mx=0,int _cst=0) { t=_t,mx=_mx,cst=_cst; } inline bool operator < (const dat &tmp) const { return t<tmp.t; } }A[N]; #define fir first #define sec second ll solve() { ll ans=0; map <int,int> mp; int now=C0; mp[0]=C0; // now 是当前系统里的水量 for(int i=1;i<=n;i++) { int dis=A[i].t-A[i-1].t;//时间差 // 注意当前处理的时间区间是 [ A[i-1].t , A[i].t ), 左闭右开 while(dis && !mp.empty())//用当前最便宜的水 { int mx=min( mp.begin()->sec , dis ); mp.begin()->sec -= mx; dis-=mx; now-=mx; ans+=1ll*mp.begin()->fir * mx;//用了才计算价钱 if(!mp.begin()->sec) mp.erase(mp.begin()); } if(dis) return -1;//没水了 int New=min( Cap-now , A[i].mx );//多出的水 now+=New;//加满 while( New<A[i].mx && !mp.empty() && mp.rbegin()->fir > A[i].cst )//考虑替换原本系统里比较贵的水 { int mx=min( mp.rbegin()->sec , A[i].mx-New ); mp.rbegin()->sec -= mx; New+=mx; if(!mp.rbegin()->sec) mp.erase( --mp.end() ); } mp[A[i].cst]+=New; } return ans; } int main() { Q=read(); while(Q--) { n=read(),m=read(),Cap=read(),C0=read(); for(int i=1;i<=n;i++) A[i].t=read(),A[i].mx=read(),A[i].cst=read(); A[++n]=dat(m,0,0);//注意细节 sort(A+1,A+n+1); printf("%lld ",solve()); } return 0; }