分析
这个东西相当于洞有容量上限和额外代价,因此可以考虑模拟费用流。
我们维护两个堆,分别代表洞和老鼠,然后从左往右扫
- 如果当前是老鼠,取出一个代价最小的洞,代价即为 $x+cost$;后面有可能反悔,即让右边的一个洞匹配这只老鼠,所以要向老鼠堆中加入 $-(x+cost)-x$。
- 如果当前是洞,取出一只代价最小的老鼠,代价即为 $y+cost+w$;后面有可能反悔,即让右边的一只老鼠匹配这个洞,所以要向洞堆中加入 $-(y+cost+w)-y+w$;还有可能让右边的一个洞匹配当前的洞匹配的老鼠,因此还要向老鼠堆中加入 $-y-w$。如果当前的洞匹配完后还有剩余容量也要加入洞堆中。
然而这样子可能向洞堆中加入 $\sum c_i$ 个元素,所以我们在堆中存一个 pair
,记下代价和出现次数即可。又因为一个匹配中的老鼠和堆不会同时反悔,所以只会操作 $\mathcal{O}(n)$ 次,故时间复杂度 $\mathcal{O}(n\log n)$。
代码
看到了一个神奇的 mutable
的写法,于是学习了一下。
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;
int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=100000+10;
const int inf=0x3f3f3f3f;
int n,m,x[N],y[N],w[N],c[N];
struct node { ll cost; mutable int cnt; };
bool operator <(node a,node b) { return a.cost>b.cost; }
priority_queue<node> M,H;
ll ans=0;
void addmouse(int x) {
ll cost=inf;
if (!H.empty()) {
cost=H.top().cost+x;
if (!(--H.top().cnt)) H.pop();
}
ans+=cost,M.push((node){-cost-x,1});
}
void addhole(int y,int w,int c) {
int s=0;
while (!M.empty()&&s<c) {
ll cost=M.top().cost+y+w;
if (cost>=0) break;
int f=min(M.top().cnt,c-s);
ans+=cost*f,s+=f,H.push((node){-cost-y+w,f});
if (!(M.top().cnt-=f)) M.pop();
}
if (s) M.push((node){-y-w,s});
if (c-s) H.push((node){-y+w,c-s});
}
int main() {
n=read(),m=read(); ll s=0;
for (int i=1;i<=n;++i) x[i]=read();
for (int i=1;i<=m;++i) y[i]=read(),w[i]=read(),c[i]=read(),s+=c[i];
if (s<n) { puts("-1"); return 0; }
for (int i=1,j=1;i<=n||j<=m;) {
if (i<=n&&(j>m||x[i]<y[j])) addmouse(x[i]),++i;
else addhole(y[j],w[j],c[j]),++j;
}
printf("%lld\n",ans);
return 0;
}
1 条评论
一直在研究这道题,难得有这么好的码风,感谢楼主!!!