[ 10.05 ]CF每日一题系列—— 962B贪心和思维？

Description：

　　非 * 号的地方可以放A或B，不能AA或BB，一共有a个A，b个B，问你最多放几个

Solution：
　　1.模拟一下，找连续空位长度，如果长度为奇数，则我可以有一个位置放任意一个，否则摆放消耗一定，最后放完了判断一下是不是还有剩下的，有剩下的就都放到任意位置
　　Code

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn = 2e5 + 2e2;

char s[maxn];

int main()

{

    int n,a,b;

    int numa,numb;

    while(~scanf("%d%d%d",&n,&a,&b))

    {

        numa = a;

        numb = b;

        scanf("%s",s);

        s[n] = '*';

        s[n+1]='\0';

        int last = -1;

        int use = 0;

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

        {

            if(s[i] == '*')

            {

                int len = i - last - 1;

                if(len & 1)use++;

                a -= len / 2;

                b -= len / 2;

                last = i;

            }

        }

        int ret = 0;

        if(a <= 0)

        {

            ret += numa;

            a = 0;

        }

        else ret += numa - a;

        if(b <= 0)

        {

            ret += numb;

            b = 0;

        }

        else ret += numb - b;

        ret += min(a+b,use);

        printf("%d\n",ret);

    }

    return 0;

}

　　2.小贪心，按位置模拟，能放的时候就先放个数最多，直到结束

　　code

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 2e5 + 2e2;
char s[maxn];
int main()
{
    int n,a,b;
    while(~scanf("%d%d%d",&n,&a,&b))
    {
        scanf("%s",s);
        int ret = 0;

        for(int i = 0;i < n;++i)
        {
            if(a < b)
                swap(a,b);
            while(s[i] == '.' && i < n)
            {
                if(a > 0)ret++;
                a--;
                swap(a,b);
                i++;
            }
        }
        printf("%d\n",ret);
    }
    return 0;
}

巴特西

[ 10.05 ]CF每日一题系列—— 962B贪心和思维？

最新文章

热门文章