1 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=5e3+5; int n,len; int a[N]; vector<int>A,B;//STL真香 int main() { scanf("%d",&n); for(int i=0;i<n;++i) scanf("%d",a+i), A.push_back(a[i]); //b[]的顺序并不影响结果 for(int i=0,b;i<n;++i) scanf("%d",&b), B.push_back(b); sort(A.begin(),A.end()); sort(B.begin(),B.end()); //朴素的贪心求最大值 for(int i=1;i<=n;++i) { bool flag=1; for(int j=0;j<i&&flag;++j) flag&=A[i-j-1]<B[n-j-1]; if(flag) len=i; else break; } //考虑字典序的因素 //所以肯定是在不影响最大匹配数的情况下,令当前的匹配数尽可能的大 for(int i=0;i<n;++i) { int pos_a=lower_bound(A.begin(),A.end(),a[i])-A.begin(); if(pos_a<len) //pos_a 本来就可以被匹配 { //从b可以匹配的最小位置开始 int pos_b=B.size()-(len-pos_a),cur=pos_a; //考虑将当前的b和后面的a进行匹配,必然使答案更优 while(pos_b+1<B.size()&&B[pos_b]>A[cur+1]) ++pos_b,++cur; --len; printf("%d ",B[pos_b]); A.erase(A.begin()+pos_a); B.erase(B.begin()+pos_b); } else// pos_a 本来不能被匹配 { //从b不能匹配的最大位置开始 a从最小数开始 int pos_b=B.size()-len-1,cur_a=0,cur_b=pos_b; ///尝试将这个数匹配上一个更大的数,必然使答案更优 //此时没有改变匹配最大值,只是换了个位置匹配 bool flag=1; while(cur_b+1<B.size()) { flag&=B[cur_b]>A[cur_a]; ++cur_b,++cur_a; //要么是把匹配位置整体后移||找到可以匹配的进行替换 if(flag||B[cur_b]>A[pos_a]) pos_b=cur_b; } printf("%d ",B[pos_b]); len-=B[pos_b]>A[pos_a]; A.erase(A.begin()+pos_a); B.erase(B.begin()+pos_b); } } return 0; }
- 1
信息
- ID
- 458
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 16
- 已通过
- 2
- 上传者