洛谷 P2587 [ZJOI2008]泡泡堂 貪心

題目：

https://www.luogu.org/problem/show?pid=2587

Q

思路：

典型的田忌賽馬型貪心；

貪心政策：

盡可能讓強的赢；

對于a[],b[];

if a[]min > b[]min ,ans+=2;

else if a[]max>b[]max ,ans+=2;

else a[]min 和 b[]max 一組；

n*2是雙方得分的總分;

是以己方的最小得分=總分-對方的最大得分；

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN=;
int a[MAXN],b[MAXN],n;
int fi(int s1[],int s2[])
{
    int l1=,l2=,r1=n,r2=n,ans=;
    while(l1<=r1 && l2<=r2)
    {
        if(s1[l1]>s2[l2]) l1++,l2++,ans+=;
        else if(s1[r1]>s2[r2]) r1--,r2--,ans+=;
        else  ans+=(s1[l1]==s2[r2]),l1++,r2--;
    }
    return ans;
}
void solve()
{
    cin>>n;
    for(int i=;i<=n;i++) scanf("%d",&a[i]);
    for(int j=;j<=n;j++) scanf("%d",&b[j]);
    sort(a+,a+n+),sort(b+,b+n+);
    printf("%d %d",fi(a,b),(n<<)-fi(b,a));
}
int main()
{
    solve();
    return ;
}