bzoj 1034 [ ZJOI 2008 ] 泡泡堂BNB —

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1034

一开始想了个很麻烦的贪心做法，对于每个 a[i]，找第一个大于它的 b 匹配……

然后WA...因为这样好像没有利用不能第一次匹配的值使答案更优；

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int const maxn=1e5+;

int n,a[maxn],b[maxn],mx,mn;

bool vis1[maxn];

priority_queue<int>q;

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 t=;

    for(int i=;i<=n;i++)

    {

        while(b[t]<=a[i]&&t<=n)q.push(b[t]),t++;

        if(t>n)break;

        vis1[i]=; t++;

    }

    for(int i=;i<=n;i++)

    {

        if(vis1[i])continue;

        int x=q.top(); q.pop();

        if(a[i]==x)mn++;

        else mn+=;

    }

    memset(vis1,,sizeof vis1);

    while(q.size())q.pop();

    t=n;

    for(int i=n;i;i--)

    {

        while(b[t]>=a[i]&&t)q.push(-b[t]),t--;

        if(!t)break;

        vis1[i]=; t--; mx+=;

    }

    for(int i=n;i;i--)

    {

        if(vis1[i])continue;

        int x=-q.top(); q.pop();

        if(a[i]==x)mx++;

    }

    printf("%d %d",mx,mn);

    return ;

}

囧

优美的正解贪心不是全局考虑，而是每次考虑最大值和最小值；

如果最小值能盖过对方的最小值或最大值能盖过对方的最大值，就直接进行；

不行就用自己的最小值匹配对方的最大值，让答案最优。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int const maxn=1e5+;

int n,a[maxn],b[maxn];

int solve(int a[],int b[])

{

    int ans=,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 ans+=(a[l1]==b[r2]),l1++,r2--;//

    }

    return 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+);

    printf("%d %d",solve(a,b),*n-solve(b,a));

    return ;

}

巴特西

bzoj 1034 [ ZJOI 2008 ] 泡泡堂BNB —— 贪心

最新文章

热门文章