义乌中学暑假集训 2021.07.16 D

(Updated: )
oi

有一天 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;
}