题解 P6179 【[USACO15DEC]High Card Wins S】

· · 题解

Solution1: 36pts

第一眼过去，一看就是带有简单决策的模拟。

那么，手动模拟怎么做呢？对于样例给出的输入，先将其排序，得到E和B的手牌：
E 1 4 6
B 2 3 5

从B的最小手牌2开始，对E的手牌由大到小进行遍历，若遇到比该牌小的牌，ans++，同时对这张E的手牌进行标记，不再进行比较。

那么，在循环到手牌2时，发现E的第一张手牌1比2小，于是v[e[1]]=true且ans++。

接着我们发现，B的第二张手牌已经是全场最小的牌。于是与当前E手中最大的牌极限一换一，v[e[3]]=true。

显然，经过n次循环，问题就能全部解决。可这种算法的时间在O(n^2)左右徘徊，很显然是过不了的。

暴力打下去，拿了36分，代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int ans,i,j,n,m,tmp,tail,cnt;
int a[100010],b[100010];
bool v[100010];
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&b[i]);
        v[b[i]]=true;
    }
    sort(b+1,b+n+1);
    for(i=1;i<=2*n;i++)
    {
        if(!v[i])
        {
            cnt++;
            a[cnt]=i;
        }
        if(cnt==n)
        {
            break;
        }
    }
    tail=n+1;
    for(i=1;i<=n;i++)
    {
        for(j=n;j>=1;j--)
        {
            if(b[j]!=-1&&a[i]>b[j])
            {
                ans++;
                b[j]=-1;
                break;
            }
        }
        if(tmp==ans)
        {
            do
            {
                tail--;
            }
            while(b[tail]==-1);
            b[tail]=-1;

        }
        tmp=ans;
    }
    printf("%d",ans);
}

Solution2: 100pts

暴力只拿了36分，在模拟方式上也没有太大的改进空间。这时我们发现在实现模拟的过程中有很多无用的操作：对最小数的“极限一换一”处理并没有在决策上起到任何帮助；对E手中的牌的标记没有记录下来的必要。即对于B的一张牌，只要知道它有赢面即可，不用精确到每一张牌的决策。

经过简化，我们可以将操作流程理解为：对B手中的所有牌进行遍历，找出所有在E手中比他小且未曾被使用过的牌，cnt++。若当前cnt>0，则cnt--并将ans++。

显然，若仍继续使用原先的储存结构，实现过程将会很难办。我们可以很容易地想到用桶来储存。

输入时用bool型的v[]来记录E的手牌。接着进行2n次循环：对于每一次循环，若v[i]==true，则cnt++，表示对于当前的牌，E手中共有cnt张手牌没被使用且比当前的牌小。

若!v[i]，表示i为B的手牌，则对cnt进行判断；若cnt>0，则表示该牌有赢面，于是ans++,E手中可取用的手牌少了一张，cnt--。

因为使用桶的方式进行储存，所以在进行遍历时数列本身是有序的，在记录cnt的值时非常便捷。可以看出，该算法的时间接近于O(n)，完全可以通过本题。

AC代码如下：

#include<cstdio>
int ans,i,j,n,m,tmp,tail,cnt,b;
bool v[100010];
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&b);
        v[b]=true;
    }
    for(i=1;i<=2*n;i++)
    {
        if(!v[i])
        {
            if(cnt>0)
            {
                cnt--;
                ans++;
            }
        }
        else
        {
            cnt++;
        }
    }
    printf("%d",ans);
}