题解 P4694 【[PA2013]Raper】

· · 题解

c老师好强啊……

线段树是不可能线段树的，这辈子都不可能线段树的

这里介绍一个代码量极短但是很垃圾的O(nlog^2n)做法

前置芝士:dp凸优化/带权二分/wqs二分

蛤？都8120年了还有人不会wqs二分？

不会的出门左转林克卡特树包教包会

本题题解

我们令f(k)表示恰好生成k个光盘的最优解，本着大胆猜想绝不求证的想法，我们猜测答案是个凸函数

(从加了hack数据还是没有叉掉这个做法这点就能说明他是凸的了)

好了现在既然答案是个凸函数我们又想要求f(k)

那么我们自然是定义一个函数G(n,t)=f(n)+nt然后求出当n取何值时G(n,t)有最小值，如果有多个n满足条件，我们选择最小的那个n

上面的过程等价于使用一条斜率恰好为t的直线去切我们的凸函数，最后求出一个切点的过程，由于答案函数是凸的因此我们知道道对于每一个点(n,f(n))，总是存在一个斜率t使得斜率为t的直线在这个凸包的切点是(n,f(n)),并且随着t的单调增加，最优决策点n的位置单调左移，这就启示我们二分斜率t然后找切点

具体来讲我们需要找到最小的t使得最优决策点的横坐标小于等于k，小于等于是因为这个直线可能会和凸包会有多个交点，按照算法流程我们选择的决策点将可能会小于k而不是等于

如此这般二分我们将会得到一条直线y=tx+b，将x=k带入即可出解，因为这个直线过(k,f(k))这个点

好了现在的问题是如何求出G(n,t)=f(n)+nt的最大值

换句话讲，没了必须选择k个的限制而是改为每一张光盘有t的额外代价(请注意这个代价必须是负的)求最小代价

那么此时我们就可以使用带反悔的贪心(有人叫模拟费用流?笑)来解决这个问题了

我们考从左到右扫一遍序列，依次插入a,b这样的好处就是当我们插入每一个b的时候之前的所有a都可以和他匹配

我们使用一个小根堆来存储所有的a点，当我们插入一个b的时候，从堆里拽出来一个a尝试和他匹配

如果匹配之后会使答案变大，那么我们直接忽略这个b,什么也不做

如果匹配之后会是答案变小，我们将a和b匹配,但是注意到后面可能会有更加优秀的b来替换这组匹配使得答案变得更加优秀，那么此时我们可以将a的权值更改为-b-t,然后接着将a丢到堆里，

这样如果我们拽出来一个已经被匹配的a，那么我们给答案加上a的权值的时候之前所匹配的b就被自动撤销了

当然啦你需要维护下拽出来的a到底是已经配过b的还是没配过b的，以便我们统计到底出现了几对匹配

顺便说一句刚才的算法丢到有k限制的时候是错的，因为我们需要考虑匹配的对数是否超过k了，如果超过k了我们就需要扔一对最大的匹配，而堆是没办法处理这样的问题的

上代码~

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;const int N=5*1e5+10;typedef long long ll;
struct data
{
    ll val;int tp;
    friend bool operator <(data a,data b)//存储权值以及是否被匹配过 
    {return (a.val==b.val)?a.tp>b.tp:a.val>b.val;}
};priority_queue <data> pq;int n;int k;ll a[N];ll b[N];ll nk;
inline ll jud(int& cnt)//计算函数 
{
    cnt=0;ll ret=0;
    for(int i=1;i<=n;i++)
    {
        pq.push((data){a[i],1});data nw=pq.top();ll del=b[i]+nw.val+nk;
        if(del<0)ret+=del,cnt+=nw.tp,pq.pop(),pq.push((data){-nk-b[i],0});
    }priority_queue <data> emp;swap(emp,pq);return ret;
}int main()
{
    scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);int tmp;
    for(int i=1;i<=n;i++)scanf("%lld",&b[i]);ll l=-(1LL<<31);ll r=0;
    while(l!=r)//二分 
    {
        ll mid=(l+r-1)/2;nk=mid;int cnt=0;
        jud(cnt);if(cnt<=k)r=mid;else l=mid+1;
    }nk=l;printf("%lld",jud(tmp)-(ll)l*k);return 0;//拜拜程序~ 
}