CF802O April Fools' Problem (hard)（题解）

· · 题解

Before Read.

前置：CF802N 的费用流做法（
upd on 5.6 修正了一个字符的错别字

Description.

见题目翻译

Solution.

感谢 @\color{black}\text{F}\color{red}\text{lying2018} 对笔者的指导。
首先，它是一个费用流模型（见 CF802N 的题解。

如果是一个费用流模型，它肯定具有下凸性
因为费用流的过程中，肯定是先增广最短路，增广完了之后不可能增广更短的路
——\color{black}\text{F}\color{red}\text{lying2018}

所以我们可以直接用类似 wqs二分 一样的套路二分一个差值。
每次可以 O(n\log n) 判断可以选多少。
具体就是当前这个点有两种决策：

  1. 把它当作 a
  2. 把它当作 b 并和之前最小的 a 匹配

可以用一个堆来维护。

Coding.

代码很短

//愿你和你重要的人能够重逢！
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &x)
{
    x=0;char c=getchar(),f=0;
    for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
    for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    f?x=-x:0;
}
int n,K,a[500005],b[500005];priority_queue<pair<int,int> >q;
int main()
{
    read(n),read(K);for(int i=1;i<=n;i++) read(a[i]);
    long long l=0,r=2e9,md;for(int i=1;i<=n;i++) read(b[i]);
    while(l<=r)
    {
        md=(l+r)>>1;long long s=0;int cnt=0;
        for(int i=1;i<=n;i++)
        {
            q.push(make_pair(-a[i],0));
            int tmp=b[i]-md-q.top().first;
            if(tmp<0) s+=tmp,q.pop(),q.push(make_pair(b[i]-md,1));
        }
        while(!q.empty()) cnt+=q.top().second,q.pop();
        if(cnt==K) return printf("%lld\n",s+1ll*K*md),0;
        if(cnt<K) l=md+1;else r=md-1;
    }
}