bzoj 1034 泡泡堂BNB

时间:2022-02-22 18:10:50

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1034

题解:
  很明显的贪心,读过田忌赛马的典故就很容易能想出来,分成三种情况讨论:

  <1>如果A队实力最强的选手比B队实力最强的选手强,就比一场;

  <2>如果A队实力最弱的选手比B队实力最弱的选手强,就比一场;

  <3>如果上述情况都不行,就直接用A队实力最弱的选手和B队实力最强的选手比一场;

  先把浙江队当成A队,对手当成B队,算出最大得分;

  再反过来算出最小得分即可

 #include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 100010
int n,a[MAXN],b[MAXN],ans;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
for(int i=;i<=n;i++)scanf("%d",&b[i]);
sort(a+,a++n);
sort(b+,b++n);
int l1=,l2=,r1=n,r2=n;
while(l1<=r1&&l2<=r2)
{
if(a[l1]>b[l2])
{
ans+=;
l1++;
l2++;
}
else if(a[r1]>b[r2])
{
ans+=;
r1--;
r2--;
}
else
{
if(a[l1]==b[r2])ans++;
l1++;
r2--;
}
}
printf("%d ",ans);
ans=;
l1=;
l2=;
r1=n;
r2=n;
while(l1<=r1&&l2<=r2)
{
if(b[l1]>a[l2])
{
ans+=;
l1++;
l2++;
}
else if(b[r1]>a[r2])
{
ans+=;
r1--;
r2--;
}
else
{
if(b[l1]==a[r2])ans++;
l1++;
r2--;
}
}
printf("%d\n",*n-ans);
return ;
}