这题显然可以等价于要找一个 \([1,n]\) 和 \([n+1,2n]\) 之间的完美匹配,但是匹配的边随着\(t\)的变化也会不断变化
所以先要发现一个结论:一组合法的方案如果是在\(t\)时刻结束,那么一定存在一个交换次数不劣于当前方案的方案,满足这个方案里的交换只发生在时刻 \(0\) 或时刻 \(t\) .证明的话,首先我们可以对这个方案里的每一组匹配 \(i\to j\) 分开考虑:
- 如果在时刻 \(0\) 或时刻 \(t\),\(i\) 的价格 \(\ge j\) 的价格,那么可以使用一次交换解决
- 否则说明我们需要在中途先依次换成若干个别的元素,显然这一定满足满足第一个元素在时刻 \(0\) 的价格 \(\le i\)的价格,最后一个元素在时刻 \(t\) 的价格 \(\ge j\) 价格.进一步的可以发现其实最多只要经过一个元素,因为对于一个中转元素集合,如果所有元素不同时满足在时刻 \(0\) 的价格 \(\le i\)的价格,在时刻 \(t\) 的价格 \(\ge j\) 价格这两个条件,那么 \(i\) 是无法转移到 \(j\) 的,即只满足前者的元素和只满足后者的元素两两无交
那么先考虑第一问,先二分答案所在时刻,然后贪心的考虑,对于某个之前的元素,如果我们在到达时刻 \(t\) 的时候的它所对应的中转元素价格越高,那么就越有利于匹配,所以先把所有元素按照在时刻 \(0\) 时的价格从小到大排序,然后每个 \([1,n]\) 里的元素选择价格不超过它的且在时刻 \(t\) 时的价格最大的元素先换过去;接着把所有元素按照在时刻 \(t\) 时的价格从大到小排序,再扫一遍,看每个 \([n+1,2n]\) 的元素是否可以找到未匹配的价格不小于它的元素匹配
然后是第二问,由于是匹配模型,我们考虑费用流,对每个点建左点右点,然后左点向右点连费用为 \(0\) 的边,\(s\) 连 \([1,n]\) 里的左点,\([n+1,2n]\) 里的右点连 \(t\) .如果 \(i\) 可以在时刻 \(0\) 换成 \(j\) ,那么左点里面连 \(1\) 费用的 \(i\to j\) 边,如果 \(i\) 可以在时刻 \(t\) 换成 \(j\) ,那么右点里面连 \(1\) 费用的 \(i\to j\) 边.注意到空间限制不允许,但是因为 \(i\to j\) 代表 \(i\) 的价格更高,那么可以按价格从小往大扫,一个点向前面的点连边即可
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=4400+10,NN=N<<2,M=NN*15,inf=1145141;
int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
return x*w;
}
int to[M],nt[M],c[M],w[M],hd[NN],tot=1;
void adde(int x,int y,int z,int zz)
{
++tot,to[tot]=y,nt[tot]=hd[x],c[tot]=z,w[tot]= zz,hd[x]=tot;
++tot,to[tot]=x,nt[tot]=hd[y],c[tot]=0,w[tot]=-zz,hd[y]=tot;
}
int di[NN],a2,pr[NN],fw[NN],ps,pt,tt;
bool vs[NN];
void csfl()
{
queue<int> q;
while(1)
{
memset(di,0x3f3f3f,sizeof(int)*(tt+1));
fw[ps]=inf,fw[pt]=0;
di[ps]=0,vs[ps]=1,q.push(ps);
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(c[i]>0&&di[y]>di[x]+w[i])
{
di[y]=di[x]+w[i];
pr[y]=i,fw[y]=min(fw[x],c[i]);
if(!vs[y]) vs[y]=1,q.push(y);
}
}
vs[x]=0;
}
if(!fw[pt]) return;
a2+=di[pt]*fw[pt];
int x=pt;
while(x!=ps)
{
int i=pr[x];
c[i]-=fw[pt],c[i^1]+=fw[pt];
x=to[i^1];
}
}
}
int n,nn,s1[N],s2[N],cn[N];
LL a[N],b[N],a1=-1,l,r,ti;
LL nps(int i,LL t){return a[i]*t+b[i];}
bool cmp1(int aa,int bb){return b[aa]!=b[bb]?b[aa]<b[bb]:a[aa]>a[bb];}
bool cmp2(int aa,int bb){return nps(aa,ti)<nps(bb,ti);}
int main()
{
/////
n=rd(),nn=n+n;
for(int i=1;i<=nn;++i) a[i]=rd(),b[i]=rd();
for(int i=1;i<=nn;++i) s1[i]=s2[i]=i;
sort(s1+1,s1+nn+1,cmp1);
l=0,r=1e9+10;
while(l<=r)
{
ti=(l+r)>>1;
for(int i=1;i<=nn;++i) cn[i]=0;
for(int i=1,j=0;i<=nn;++i)
{
int x=s1[i];
if(!j||nps(x,ti)>nps(j,ti)) j=x;
if(x<=n) ++cn[j];
}
sort(s2+1,s2+nn+1,cmp2);
int nw=0;
for(int i=nn,j=nn;i;--j,i=j)
{
while(j>1&&nps(s2[i],ti)==nps(s2[j-1],ti)) --j;
for(int k=i;k>=j;--k) nw+=cn[s2[k]];
for(int k=i;k>=j;--k) nw-=s2[k]>n;
if(nw<0) break;
}
if(nw>=0) a1=ti,r=ti-1;
else l=ti+1;
}
if(a1==-1){printf("%lld\n",a1);return 0;}
ps=0,tt=pt=nn+nn+2;
for(int i=1;i<=nn;++i)
{
if(i<=n) adde(ps,i,1,0);
else adde(i+nn,pt,1,0);
adde(i,i+nn,inf,0);
}
ti=a1,sort(s2+1,s2+nn+1,cmp2);
for(int i=1,j=1,lp=++tt;i<=nn;++j,i=j)
{
while(j<nn&&b[s1[i]]==b[s1[j+1]]) ++j;
int np=++tt;
for(int k=i;k<=j;++k) adde(s1[k],np,inf,1);
for(int k=i;k<=j;++k) adde(np,s1[k],inf,0);
adde(np,lp,inf,0),lp=np;
}
for(int i=1,j=1,lp=++tt;i<=nn;++j,i=j)
{
while(j<nn&&nps(s2[i],ti)==nps(s2[j+1],ti)) ++j;
int np=++tt;
for(int k=i;k<=j;++k) adde(s2[k]+nn,np,inf,1);
for(int k=i;k<=j;++k) adde(np,s2[k]+nn,inf,0);
adde(np,lp,inf,0),lp=np;
}
csfl();
printf("%lld %d\n",a1,a2);
return 0;
}