义乌中学暑假集训 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)$。

#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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇