shadowice1984 的博客

shadowice1984 的博客

题解 P4694 【[PA2013]Raper】

posted on 2019-03-21 21:12:36 | under 题解 |

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;//拜拜程序~ 
}