二分答案。
思路:对于二分给定的mid,即当前允许移动的最大重量,我们可以把小于改重量的标记一下,然后把没有标记的按照顺序放到另一个数组,然后判断是否满足两两相同。
#include<bits/stdc++.h>
using namespace std;
const int N=1E6+;
int arr[N];
int brr[N];
int crr[N];
bool mark[N],mark1[N];
const int INF=1e9+;
const int mm=1e9;
int n;bool judge(int x){
memset(mark,,sizeof(mark));
memset(mark1,,sizeof(mark1)); for(int i=;i<=n;i++) {
if(arr[i]<=x) mark[i]=;
if(brr[i]<=x) mark1[i]=;
} int pos=;
for(int i=;i<=n;i++){
if(mark[i]==) crr[++pos]=arr[i];
} if(pos&) return ;
for(int i=;i<=pos;i+=){
if(crr[i]!=crr[i+]) return ;
}
pos=;
for(int i=;i<=n;i++){
if(mark1[i]==) crr[++pos]=brr[i];
}
if(pos&) return ;
for(int i=;i<=pos;i+=) {
if(crr[i]!=crr[i+]) return ;
}
return ;
}void solve(){
cin>>n;
for(int i=;i<=n;i++) scanf("%d",&arr[i]);
for(int j=;j<=n;j++) scanf("%d",&brr[j]);
int l=,r=mm;
int ans=INF;
while(l<=r){
int mid=(l+r)/;
if(judge(mid)){
r=mid-;
ans=min(ans,mid);
}
else l=mid+;
} cout<<ans<<endl;
}int main(){
solve();
return ;
}