题意：有一个单行走廊，每回合第a_i个展柜会冒出来一只鬼，右边尽头有一个人间大炮和向最左传送门（费用均1金币），你需要每回合将所有鬼交换展柜，全部至最右，问若从一到n所有回合结束是需多少金币可射死所有鬼。

思路：花一块可将一只鬼挪至最右，然后使用一个指针储蓄最右有几个鬼，然后相减就可以了。

见代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

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

bool c[];

int main()

{

    freopen("coin.in","r",stdin);

    freopen("coin.out","w",stdout);

    cin>>n;

    k=n;

    b[]=;

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

    {

        cin>>a[i];

        c[a[i]]=true;

        if(a[i]==k)

        {

            while(c[k]==true)

            k--;

            if(k==n-i)

            b[i]=;

            else

            b[i]=b[i-];

        }

        else

        b[i]=+b[i-];

    }

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

    cout<<b[i]<<" ";

    return ;

}

又双叒叕炸掉了！

原因是部分在右部分不在右的情况未考虑清。

见代码*2：

#include<iostream>

using namespace std;

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

bool c[];

int main()

{

    cin>>n;

    k=n;

    b[]=;

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

    {

        cin>>a[i];

        c[a[i]]=true;

        b[i]=b[i-]+;

        if(a[i]==k)

        {

            while(c[k]==true)

            {

                b[i]--;

                k--;

            }

        }

    }

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

    cout<<b[i]<<" ";

    return ;

}

巴特西

嵊州普及Day4T2

好题哉！！！

最新文章

热门文章