cdqz 两道题都很有意思啊！顺便是第一篇 *3500 题解。
先考虑第一问。
显然有单调性，所以可以二分。cdqz 这是二分专题吗
Lemma 1：所有操作都在 \(0\) 和 \(t\) 时刻进行。
Proof：这是若干个一次函数，最大或最小值都会在端点处取得。所以是显然的。
接下来你就要使你在 \(t\) 时刻所拥有的股票价值尽可能大。所以在 \(0\) 时刻把所有股票换成能换的价值尽可能大的股票即可。看实现可以做到 \(O(n^2)\) 或 \(O(n\log n)\) 完成 check。
接下来考虑第二问。发现每个 \([1,n]\) 的股票都对应一个 \([n+1,n\times 2]\) 中的。这使我们想到什么？二分图匹配。考虑网络流建模，跑 MCMF 解决。
首先每个股票有 \(0\) 时刻和 \(t\) 时刻两个状态，所以拆成两个点 \(a0_i,at_i\)。
然后是连基本的 \((S,a0_i,1,0)(i\le n),(at_i,T,1,0)(i>n),(a0_i,at_i,inf,0)\)。
最后就要刻画 \(0,t\) 时刻的换股票。一个 trival 的想法是枚举两个点 \(a_i,a_j\) 如果此时股票 \(i\) 的价值大于股票 \(j\) 的，那么可以换，即连 \((a_i,a_i,inf,1)\)。
但是这样的时空是 \(O(n^2)\) 的，就算时间可以空间也不行。但是发现每次连的是排序后的一段前缀。所以可以前缀和优化建图。具体就是新增点 \(s0_i,st_i\)，排序后连 \((s0_i,s0_{i-1},inf,0),(s0_i,a0_i,inf,0),(a0_i,s0_{i-1},inf,0)\)。\(t\) 时刻同理。
然后跑 dinic 就做完了。
做起来感觉反而不难。
复杂度 \(O(n\log n\log v+\operatorname{maxflow})\)。后者远远顶不到时间复杂度上界。
我的常数怎么这么小？目前是最优解。就看 zlt 什么时候做完把我踢下去了。
有一点点小细节，就是排序的 cmp 要注意相等时的顺序，否则会 WA on test 113。
code：
点击查看代码
int n,m,nt,sum,dis[M],cur[M];
pair<ll,int> c[N];bool vis[M];
static int S,T;
int tot=1,head[M];
struct node{int to,nxt,fl,cw;}e[M<<1];
struct Node{int k,b,op;}a[N];
il void add(int u,int v,int f,int w){
e[++tot]={v,head[u],f,w},head[u]=tot;
e[++tot]={u,head[v],0,-w},head[v]=tot;
}
il ll calc(Node x,int y){return 1ll*x.k*y+x.b;}
il bool cmp1(Node x,Node y){return calc(x,0)==calc(y,0)?calc(x,nt)>calc(y,nt):calc(x,0)<calc(y,0);}
il bool cmp2(Node x,Node y){return calc(x,nt)>calc(y,nt);}
il bool cmp3(pair<ll,int> x,pair<ll,int> y){return x.fi==y.fi?a[x.se].op>a[y.se].op:x.fi<y.fi;}
bool check(int t){
ll mx=-1ll*inf*inf;nt=t;
priority_queue<ll> q;
sort(a+1,a+n*2+1,cmp1);
rep(i,1,n*2){
mx=max(mx,calc(a[i],t));
if(!a[i].op)q.push(mx);
}
sort(a+1,a+n*2+1,cmp2);
rep(i,1,n*2){
if(!a[i].op)continue;
if(q.empty()||q.top()<calc(a[i],t))return 0;
q.pop();
}
return 1;
}
int solve1(){
int l=0,r=1e9,ans=1e9+1;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid))r=(ans=mid)-1;
else l=mid+1;
}
if(ans==1e9+1)puts("-1"),exit(0);
return printf("%d ",ans),ans;
}
bool spfa(){
mems(dis,0x3f),mems(vis,0);
memcpy(cur,head,sizeof head);
queue<int> q;
dis[S]=0,vis[S]=1;
q.push(S);
while(q.size()){
int u=q.front();q.pop();
vis[u]=0;
go(i,u){
int v=e[i].to;
if(!e[i].fl||dis[v]<=dis[u]+e[i].cw)continue;
dis[v]=dis[u]+e[i].cw;
if(!vis[v])vis[v]=1,q.push(v);
}
}
return dis[T]<=1e9;
}
int dfs(int u,int f){
if(u==T)return f;
int s=0;vis[u]=1;
for(int &i=cur[u];i;i=e[i].nxt){
int v=e[i].to;
if(vis[v]||!e[i].fl||dis[v]!=dis[u]+e[i].cw)continue;
int l=dfs(v,min(e[i].fl,f-s));
e[i].fl-=l,e[i^1].fl+=l;
s+=l,sum+=l*e[i].cw;
if(s==f)break;
}
vis[u]=0;
return s;
}
void dinic(){
int ret=0;
while(spfa())ret+=dfs(S,inf);
}
void solve2(int t){
S=n*8+1,T=S+1;
rep(i,1,n*2)if(!a[i].op)add(S,i,1,0);else add(n*2+i,T,1,0);
rep(i,1,n*2)add(i,n*2+i,inf,0);
rep(i,1,n*2)c[i]=Mp(calc(a[i],0),i);
sort(c+1,c+n*2+1);
add(n*4+c[1].se,c[1].se,inf,0);
rep(i,2,n*2)add(c[i].se,n*4+c[i-1].se,inf,1),add(n*4+c[i].se,n*4+c[i-1].se,inf,0),add(n*4+c[i].se,c[i].se,inf,0);
rep(i,1,n*2)c[i]=Mp(calc(a[i],t),i);
sort(c+1,c+n*2+1,cmp3);
add(n*6+c[1].se,n*2+c[1].se,inf,0);
rep(i,2,n*2)add(n*2+c[i].se,n*6+c[i-1].se,inf,1),add(n*6+c[i].se,n*6+c[i-1].se,inf,0),add(n*6+c[i].se,n*2+c[i].se,inf,0);
dinic(),printf("%d\n",sum);
}
void Yorushika(){
scanf("%d",&n);
rep(i,1,n)scanf("%d%d",&a[i].k,&a[i].b),a[i].op=0;
rep(i,n+1,n*2)scanf("%d%d",&a[i].k,&a[i].b),a[i].op=1;
int t=solve1();solve2(t);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}