【题解】洛谷P2587 [ZJOI2008]泡泡堂

2018-03-01 09:30:56


算法

求最优->DP或贪心。 然而这题让人联想到田忌赛马,所以果断贪心。

但是田忌赛马的方式是错的,因为己方最蒻的还有可能打败敌方最蒻的,从而得到两分。

那么贪心的方式就出来了:首先判断己方的最蒻能否打败敌方的最蒻;如果不能,判断己方的最强能否打败敌方的最强;如果还不能,判断己方的最蒻能否和敌方的最强打成平局(在前面全部否的情况下一定不能赢)。

这样就求出了己方的最好分数。

注意到比赛双方一共得到了 $2n$ 分,所以只要求出敌方的最好情况 $ans$ ,然后用 $2n-ans$ 就是己方的最差分数。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}
int a[100010],b[100010];
int n;
inline int solve(int a[],int b[]) {
    int ha=1,hb=1,ta=n,tb=n,rt=0;
    while (ha<=ta) {
        if (a[ha]>b[hb]) ha++,hb++,rt+=2;
        else if (a[ta]>b[tb]) ta--,tb--,rt+=2;
        else {
            if (a[ha]==b[tb]) rt++;
            ha++,tb--;
        }
    }
    return rt;
}
int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=n;++i) b[i]=read();
    sort(a+1,a+n+1); sort(b+1,b+n+1);
    printf("%d %d\n",solve(a,b),2*n-solve(b,a));
    return 0;
}