[JZOJ5378]闷声刷大题

题目描述

分析

这道题原本是线段树模拟网络流的，但是有个东西叫凸函数优化。
设f[k]表示做k道题的代价和，那么f(k)是一个凸函数，显然，f(i-1)比f(i)要小，而f(i+1)-f(i)>f(i)-f(i-1)。我们又知道如何在不考虑做几道题限制的时候最小的代价(显然，在没有改变条件之前，什么都不选就是做法)。现在，我们可以设定一个常数c，每次匹配的代价都-c，这样，最小的代价就不一定是做0道题了。先不考虑如何贪心，分析可知，我们只要二分c，使他取一个适当的值，就能让匹配的个数是K；如果不是，也只是因为K和K-1和K+1之类的差值都一样（斜率相同），都是c，这个可以计算。
考虑贪心？一个套路是，我们把a，b合并，看成是n个括号，寻找最佳合法括号序，加入a时，往数据结构里扔a[i]-c，遇到b时，如果数据结构的最小值mn+b[i]<0，那么匹配他们，答案+mn+b[i]；然后，由于有可能后面的b可以代替b[i]，我们再把-b[i]插入回去。
做完了，两个log，难过，我开了个O2…

分析

#pragma GCC optimize(2)
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set>
using namespace std;
#define fo(i,j,k) for(i=j;i<=k;i++)
#define fd(i,j,k) for(i=j;i>=k;i--)
#define cmax(a,b) (a=(a>b)?a:b)
#define cmin(a,b) (a=(a<b)?a:b)
typedef long long ll;
typedef double db;
const int N=2e5+5;
struct rec
{ll v;int inc;
};
multiset<rec> tr;
multiset<rec> :: iterator it;
bool operator <(rec a,rec b)
{return a.v<b.v;
}
ll tmp,l,r,mid;
int a[N],b[N],cnt,n,K,i;
void run(int x)
{tmp=cnt=0;tr.clear();fo(i,1,n){tr.insert({a[i]-x,1});it=tr.begin();if ((*it).v+b[i]<0){tmp+=(*it).v+b[i];cnt+=(*it).inc;tr.erase(it);tr.insert({-b[i],0});}}
}
int main()
{freopen("t3.in","r",stdin);//freopen("orz.out","w",stdout);scanf("%d %d",&n,&K);fo(i,1,n) scanf("%d",a+i);fo(i,1,n) scanf("%d",b+i);l=0;r=2e9;while (l<r){mid=(l+r)/2;run(mid);if (cnt<K) l=mid+1;if (cnt>K) r=mid-1;if (cnt==K) l=r=mid;}run(l);if (cnt!=K) tmp+=1ll*(K-cnt)*l;tmp+=K*l;printf("%lld",tmp);
}