打卡信奥刷题（2750）用C++实现信奥题 P3657 [USACO17FEB] Why Did the Cow Cross the Road II P

P3657 [USACO17FEB] Why Did the Cow Cross the Road II P

题目背景

本题与 金组同名题目 在题意上一致，唯一的差别是数据范围。

题目描述

Farmer John 饲养了N NN种奶牛，编号从1 11到N NN。一些品种的奶牛和其他奶牛间相处良好，事实证明，如果两个品种的奶牛编号分别为a , b a,ba,b，当∣ a − b ∣ ≤ 4 |a-b| \leq 4∣a−b∣≤4时，这两个品种的奶牛能友好相处，否则不能友好相处。

一条长长的道路贯穿整个农场，道路的左侧有N NN个牧场（每个品种的奶牛恰好占据一个牧场），道路的右侧也有N NN个牧场（每个品种的奶牛恰好占据一个牧场）。为了让奶牛们安全穿过马路，Farmer John 希望能在马路上画出一些人行道（牛行道？），要求这些人行道满足如下条件：

1. 人行道从左侧的某个牧场出发，连接到右侧的某个牧场；
2. 人行道连接的两个牧场的奶牛要能友好相处；
3. 人行道不能在道路中间相交；
4. 每个牧场只能与一条人行道相连。

你需要帮 FJ 求出最多能有多少条人行道。

输入格式

输入第一行一个整数N NN（1 ≤ N ≤ 10 5 1 \leq N \leq 10^51≤N≤105）。

接下来N NN行，每行一个整数a i a_iai​，代表道路左侧第i ii个牧场的奶牛品种编号。

接下来N NN行，每行一个整数b i b_ibi​，代表道路右侧第i ii个牧场的奶牛品种编号。

输出格式

输出最多能画多少条人行道。

输入输出样例 #1

输入 #1

6 1 2 3 4 5 6 6 5 4 3 2 1

输出 #1

5

说明/提示

保证a i , b i a_i,b_iai​,bi​均为从1 11到N NN的排列。

C++实现

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;#defineregregisterinlinechargc(){staticconstintbs=1<<22;staticunsignedcharbuf[bs],*st,*ed;if(st==ed)ed=buf+fread(st=buf,1,bs,stdin);returnst==ed?EOF:*st++;}#definegcgetcharinlineintread(){intres=0;charch=gc();boolfu=0;while(!isdigit(ch))fu|=(ch=='-'),ch=gc();while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=gc();returnfu?-res:res;}#defineN100005intn;inta[N],b[N];intpos[N];intc[N*9],cnt,tmp[10];intlow[N*9],ans;intmain(){n=read();for(reginti=1;i<=n;i++)a[i]=read();for(reginti=1;i<=n;i++)pos[b[i]=read()]=i;for(reginti=1;i<=n;i++){inttop=0;for(regintj=max(1,a[i]-4);j<=min(n,a[i]+4);j++)tmp[++top]=pos[j];sort(tmp+1,tmp+1+top);for(regintj=top;j>=1;j--)c[++cnt]=tmp[j];}low[++ans]=c[1];for(reginti=2;i<=cnt;i++){if(c[i]>low[ans])low[++ans]=c[i];else{intt=lower_bound(low+1,low+1+ans,c[i])-low;low[t]=c[i];}}cout<<ans<<endl;return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容