C++(g++ 7.5.0) 解法, 执行用时: 6ms, 内存消耗: 536K, 提交时间: 2023-03-22 18:09:32

#include<bits/stdc++.h>
using namespace std;
int num[10010];
int ans[10010];
int maps[10010];
int n,m;
int sum;
void dfs(int l,int r,int sl,int sr,int index)
{
    if(l==r)
    {
        int g=sum-sl-sr;
        if(g>=1&&g<=500&&maps[g]==1)
        {
            ans[l]=g;
            for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
            exit(0);
        }
        return ;
    }
    int h=num[index]-sl;
    if(h<=500&&maps[h])
    {
        ans[l]=h;
        dfs(l+1,r,num[index],sr,index+1);
    }
    int j=num[index]-sr;
    if(j<=500&&maps[j])
    {
        ans[r]=j;
        dfs(l,r-1,sl,num[index],index+1);
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=2*n;i++)cin>>num[i];
    cin>>m;
    for(int i=1,u;i<=m;i++)
    {
        cin>>u;
        maps[u]=1;
    }
    sort(num+1,num+1+2*n);
    sum=num[2*n];
    dfs(1,n,0,0,1);
}

C++(clang++11) 解法, 执行用时: 5ms, 内存消耗: 472K, 提交时间: 2021-03-05 19:39:57

#include<bits/stdc++.h>
using namespace std;
int n,m,sum,a[2005],ans[1005];
bool S[505];
void dfs(int L,int R,int sl,int sr,int k)
{
	if(L==R)
	{
		if(sum-sl-sr<=500&&S[sum-sl-sr])
		{
			ans[L]=sum-sl-sr;
			for(int i=1;i<=n;i++)
			printf("%d ",ans[i]);
			exit(0);
		}
		return;
	}
	if(a[k]-sl<=500&&S[a[k]-sl])
	{
		ans[L]=a[k]-sl;
		dfs(L+1,R,a[k],sr,k+1);
	}
	if(a[k]-sr<=500&&S[a[k]-sr])
	{
		ans[R]=a[k]-sr;
		dfs(L,R-1,sl,a[k],k+1);
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=2*n;i++)
	cin>>a[i];
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int x;
		cin>>x;
		S[x]=1;
	}
	sort(a+1,a+2*n+1);
	sum=a[2*n];
	dfs(1,n,0,0,1);
	return 0;
}