给定数轴上 \(n\) 只老鼠和 \(m\) 组洞，第 \(i\) 只老鼠在 \(x_i\)，第 \(j\) 组洞在 \(y_j\)，有 \(c_j\) 个洞，代价是 \(w_j\)。
第 \(i\) 只老鼠进第 \(j\) 个洞的代价是 \(|x_i-y_j|+w_j\)，求每只老鼠都进洞的最小代价。
\(2\le n,m\le 10^5\)，\(0\le x_i,y_i,c_i,w_i\le 10^9\)。
模拟费用流经典题。
将所有老鼠和洞排序，并认为所有老鼠和洞都向左匹配（也即在匹配中坐标更大的位置考虑）
对老鼠和洞建堆，若当前有一只老鼠 \(x\)，则取个最优的洞 \(y\) 匹配，老鼠反悔代价是 \(-2x-y\)，而洞是不会反悔的，因为要取就取最近的。
若当前有一组洞 \(y\)，则取个最优的老鼠 \(x\)，洞反悔代价是 \(-x-2y\)，老鼠反悔代价是 \(-y-w\)。
把相同权值的元素合并，复杂度就对了！
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pii;
const int N = 100003;
template<typename T>
void rd(T &x){
int ch = getchar(); x = 0;
for(;ch < ‘0‘ || ch > ‘9‘;ch = getchar());
for(;ch >= ‘0‘ && ch <= ‘9‘;ch = getchar()) x = x * 10 + ch - ‘0‘;
}
int n, m, X[N], Y[N], W[N], C[N];
LL ans, sum;
priority_queue<pii, vector<pii>, greater<pii> > ass, hole;
void pushX(int x){
LL y = hole.empty() ? 1e14 : hole.top().fi;
ans += x+y; ass.emplace(-2*x - y, 1);
if(!hole.empty()){
LL c = hole.top().se; hole.pop();
if(c > 1) hole.emplace(y, c - 1);
}
}
void pushY(int y, int w, int c){
int mc = 0;
while(mc < c && !ass.empty() && y + w + ass.top().fi < 0){
pii _ = ass.top(); ass.pop();
int t = min((LL)c-mc, _.se);
ans += t * (_.fi + y + w);
if(t != _.se) ass.emplace(_.fi, _.se - t);
hole.emplace(-_.fi - 2*y, t); mc += t;
}
if(mc) ass.emplace(-y - w, mc);
if(mc < c) hole.emplace(w - y, c - mc);
}
int main(){
rd(n); rd(m);
for(int i = 1;i <= n;++ i) rd(X[i]);
for(int i = 1;i <= m;++ i){rd(Y[i]); rd(W[i]); rd(C[i]); sum += C[i];}
if(sum < n){puts("-1"); return 0;}
int p = 1;
for(int i = 1;i <= n;++ i){
for(;p <= m && X[i] >= Y[p];++ p) pushY(Y[p], W[p], C[p]);
pushX(X[i]);
} for(;p <= m;++ p) pushY(Y[p], W[p], C[p]);
printf("%lld\n", ans);
}