一开始是不会的,不知道如何处理相等的情况,瞎贪心一直WA。
于是就递归处理是让相等的平局还是输掉,如下,拿到了50分。
int solve(int *a,int *b,int i,int l,int r)
{
int ans=0;
for(;i<=n;++i)
{
if(a[i]>b[l])
ans+=2,++l;
else if(a[i]<b[l])
--r;
else
{
ans+=max(solve(a,b,i+1,l+1,r)+1,solve(a,b,i+1,l,r-1)+(a[i]==b[r]?1:0));
break;
}
}
return ans;
}
附正解,网上的讲解已经很完善了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=100000+5;
int a[MAXN],b[MAXN];
int n;
int solve(int *a,int *b)
{
int ans=0,la=1,lb=1,ra=n,rb=n;
while(la<=ra)
{
if(a[la]>b[lb])
{
ans+=2;
++la,++lb;
}
else if(a[ra]>b[rb])
{
ans+=2;
--ra,--rb;
}
else
{
if(a[la]==b[rb])
++ans;
++la,--rb;
}
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
for(int i=1;i<=n;++i)
scanf("%d",&b[i]);
sort(b+1,b+n+1);
printf("%d %d",solve(a,b),(n<<1)-solve(b,a));
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章