义乌中学暑假集训 2021.07.16 D

有一天 Mifafa 回到家,发现有 $n$ 只老鼠在她公寓的走廊上,她大声呼叫,所以老鼠们都跑进了走廊的洞中。

这个走廊可以用一个数轴来表示,上面有 $n$ 只老鼠和 $m$ 个老鼠洞。第 $i$ 只老鼠有一个坐标 $x_i$,第 $j$ 个洞有一个坐标 $p_j$ 和容量 $c_j$。容量表示最多能容纳的老鼠数量。

找到让老鼠们全部都进洞的方式,使得所有老鼠运动距离总和最小。

老鼠 $i$ 进入洞 $j$ 的运动距离为 $x_i−p_j$ 。

无解输出 $-1$。

$c,n,m\leq 10^6,1\leq p,x\leq 10^9$。

Sol

反悔贪心。

将所有的洞和老鼠一起按照横坐标排序,考虑一只老鼠 $i$ 如果进入了左侧离它最近的没用完的洞 $j$,若要用另一个洞 $k$ 去替换 $j$,贡献为:
$$
(p_k-x_i)-(x_i-p_j)=p_k+(-2x_i+p_j)
$$
同理对于个洞 $i$,若用另一个老鼠 $k$ 代替原有老鼠 $j$,贡献为:
$$
(x_k-p_i)-(p_i-x_j)=x_k+(-2p_i+x_j)
$$
然后开两个堆分别维护老鼠&洞,直接按照如上规则跑。

时间复杂度 $\mathcal O(n\log n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
#define I inline
#define W while
#define RI register int
#define Cn const
#define CI Cn int&
#define gc getchar
#define pc putchar
#define LL long long
using namespace std;
I void read(int& x){RI f=1;char c=gc();x=0;W(!('0'<=c&&c<='9')) f=c^'-'?f:-1,c=gc();W('0'<=c&&c<='9') x=x*10+(c-'0'),c=gc();x*=f;}
I void write(LL x){x<0&&(pc('-'),x=-x),x>=10&&(write(x/10),0),pc(x%10+'0');}
Cn int N=1e6+10;
int n,m,inf=2e9,cnt;
#define P pair<LL,int>
#define MP make_pair
#define fi first
#define se second
P b[N<<1];
LL sc,Ans;
priority_queue<LL> Q1;
priority_queue<P> Q2;
int main(){
RI i,j,x,y;LL t;for(read(n),read(m),i=1;i<=n;i++) read(x),b[++cnt]=MP(x,-1);
for(i=1;i<=m;i++) read(x),read(y),b[++cnt]=MP(x,y),sc+=y;
if(sc<n) return puts("-1"),0;
for(sort(b+1,b+cnt+1),i=1;i<=cnt;i++) if(~b[i].se){
W(!Q1.empty()&&b[i].se&&b[i].fi<Q1.top()) t=b[i].fi-Q1.top(),Q1.pop(),b[i].se--,Q2.push(MP(b[i].fi+t,0)),Ans+=t;
b[i].se&&(b[i].se--,Q2.push(MP(b[i].fi,i)),0);
}else{
t=2e12;if(!Q2.empty()) t=b[i].fi-Q2.top().fi,j=Q2.top().se,Q2.pop(),b[j].se&&(b[j].se--,Q2.push(MP(b[j].fi,j)),0);
Ans+=t,Q1.push(b[i].fi+t);
}return write(Ans),0;
}