1 条题解

  • 0
    @ 2021-8-21 17:11:09
    #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
    上传者