题解 P4694 【[PA2013]Raper】

c老师好强啊…… ~~线段树是不可能线段树的，这辈子都不可能线段树的~~ 这里介绍一个代码量极短但是很垃圾的$O(nlog^2n)$做法 ______________________ ## 前置芝士:dp凸优化/带权二分/wqs二分 蛤？都8120年了还有人不会wqs二分？ 不会的出门左转[林克卡特树](https://www.luogu.org/problemnew/show/P4383)包教包会 # 本题题解 我们令$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了我们就需要扔一对最大的匹配，而堆是没办法处理这样的问题的 上代码~ ```C #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;//拜拜程序~ } ```