【Codeforces 802N/802O】April Fools' Problem | Mrsrz's blog

贪心，凸优化。

题目大意：

给定两个长度为 $n$ 的数列 $a_1,a_2,a_3,\ldots,a_n$ 和 $b_1,b_2,b_3,\ldots,b_n$，并给定 $k$，要求选出 $i_1,i_2,i_3,\ldots,i_k$ 和 $j_1,j_2,j_3,\ldots,j_k$，满足：

• $1\leq i_1\lt i_2\lt i_3\lt \ldots\lt i_k\leq n$，$1\leq j_1\lt j_2\lt j_3\lt \ldots\lt j_k\leq n$。
• $i_1\leq j_1,i_2\leq j_2,i_3\leq j_3,\ldots,i_k\leq j_k$。
• 最小化 $a_{i_1}+a_{i_2}+a_{i_3}+\cdots+a_{i_k}+b_{j_1}+b_{j_2}+b_{j_3}+\cdots+b_{j_k}$ 的值。

求最小值。

题解：

考虑没有 $k$ 的限制的时候怎么做。

此时答案显然为 $0$，因为 $a$ 和 $b$ 都是正的。

那如果 $a$ 和 $b$ 有负数呢？

我们有以下贪心做法：

从 $n$ 到 $1$ 考虑每个 $a_i$，此时 $b_{i\sim n}$ 都是可以选的。用一个堆维护 $b_{i\sim n}$ 的最小值。

对于已经选择的 $a_i$ 和 $b_j$ 配对，我们用另一个堆维护 $-a_{i}$ 的最小值。

然后考虑新加入一个 $a_i$，先将 $b_i$ 插入堆中。

此时有三种决策：$a_i$ 和最小的 $b_j$ 配对；用 $a_i$ 替换掉一个 $-a_j$ 最小的 $a_j$；不做任何操作。

我们取最优决策即可。如果 $a_i$ 最后被选，则将 $-a_i$ 插入堆中。

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

那么这个有什么用呢？

我们考虑函数 $f(k)$ 表示选择 $k$ 对时的最小值。容易证明这是一个凸函数。

那么我们对这个算法使用凸优化即可。

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

Code：

#include<cstdio>
#include<cctype>
#include<queue>
using namespace std;
typedef long long LL;
const int N=5e5+5;
char buf[(int)1.1e8],*ss=buf;
inline int init(){buf[fread(buf,1,(int)1.1e8-1,stdin)]='\n';fclose(stdin);return 0;}
const int __START__=init();
inline int readint(){
    int d=0,f=0;
    while(!isdigit(*ss))f=*ss++=='-';
    while(isdigit(*ss))d=d*10+(*ss++^'0');
    return f?-d:d;
}
int n,a[N],b[N],k;
LL ans,ANS;
inline bool chk(int x){
    priority_queue<int>p,q;
    ANS=0;
    int cnt=0;
    for(int i=n;i;--i){
        q.push(x-b[i]);
        int s=p.empty()?-(1<<30):p.top(),t=q.top();
        if(s<t){
            if(a[i]<t)++cnt,p.push(a[i]),q.pop(),ANS+=a[i]-t;
        }else if(a[i]<s)p.pop(),p.push(a[i]),ANS+=a[i]-s;
    }
    ANS+=(LL)k*x;
    return cnt<=k;
}
int main(){
    n=readint(),k=readint();
    for(int i=1;i<=n;++i)a[i]=readint();
    for(int i=1;i<=n;++i)b[i]=readint();
    unsigned l=0,r=2e9+1;
    while(l<=r){
        const unsigned mid=l+r>>1;
        if(chk(mid))ans=ANS,l=mid+1;else r=mid-1;
    }
    printf("%lld\n",ans);
    return 0;
}