LUOGU P2587 [ZJOI2008]泡泡堂

传送门

解题思路

刚开始先写了个田忌赛马的贪心，就是要是打不过就拿最弱的送死，30分。。。后来瞄了眼题解，发现这样是错的，比如说这样的数据 ：

3

3 2

3 1

如果用田忌赛马的话，让2-3 3-1 ，这样只有两分，实际上应该是2-1 3-3 这样有3分

所以应该是强贪强，弱贪弱，都打不过拿去送。这里我用了个双端对列，懒得处理边界了。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int MAXN = 100005;

inline int rd(){

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}

    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

    return x*f;

}

int n,a[MAXN],b[MAXN],ans1,ans2;

int head=1,use[MAXN],cnt;

deque<int> Q[3];

int main(){

    n=rd();

    for(register int i=1;i<=n;i++) a[i]=rd();

    for(register int i=1;i<=n;i++) b[i]=rd();

    sort(a+1,a+1+n);sort(b+1,b+1+n);head=1;

    for(register int i=1;i<=n;i++) Q[1].push_back(a[i]),Q[2].push_back(b[i]);

    while(Q[1].size()){

        if(Q[1].front()>Q[2].front()) {ans1+=2;Q[1].pop_front();Q[2].pop_front();}

        else if(Q[1].back()>Q[2].back()) {ans1+=2;Q[1].pop_back();Q[2].pop_back();}

        else {

            if(Q[1].front()==Q[2].back()) ans1++;

            Q[1].pop_front();Q[2].pop_back();

        }

    }

    for(register int i=1;i<=n;i++) Q[1].push_back(a[i]),Q[2].push_back(b[i]);

    while(Q[1].size()){

        if(Q[1].front()<Q[2].front()) {ans2+=2;Q[1].pop_front();Q[2].pop_front();}

        else if(Q[1].back()<Q[2].back()) {ans2+=2;Q[1].pop_back();Q[2].pop_back();}

        else {

            if(Q[2].front()==Q[1].back()) ans2++;

            Q[1].pop_back();Q[2].pop_front();

        }

    }

    ans2=2*n-ans2;

    printf("%d %d",ans1,ans2);

    return 0;

}