H--唱歌的鸟儿

H--唱歌的鸟儿

时间: 1ms        内存:128M

描述:

烟大东门有一棵大杨树,树上经常会有很多鸟儿飞来飞去。春天来了,学生物的小姜发现了一些规律。在这棵杨树上,假如来了一只雄鸟,它会在树上唱歌,如果 p 分钟内有一只雌鸟飞来和它一起唱,它们就会一直呆在树上不走了,否则 p 分钟之后,这只雄鸟就会飞走。假如来的是只雌鸟,如果没有落单的雄鸟在树上,它不会落到树上而是直接飞走,否则它会选择等待时间最长的雄鸟和它一起唱歌,就再也不走了。如果在某个时刻,同时发生了鸟儿的飞进飞出,那么先有一只鸟儿飞出枝头,再由另一只鸟儿飞上枝头。
现在小姜记录了一段时间飞来这棵杨树的鸟儿,每隔一分钟可能会飞来一只雌鸟或雄鸟,或者什么都没有发生,现在小姜想知道这段时间内树上最多有多少只鸟儿,你可以帮助他吗?

输入:

首先输入一个正整数T,T <= 50,表示有T组数据。
每组第一行给出两个整数n、p,分别表示记录时间段的长度,和每个雄鸟最多能等待的时间(1 < n <= 1000,1 <= p <= 10)。
第二行为一个长度为n的字符串,由 0, 1, 2 三种字符构成,表示这段时间内鸟儿飞来的情况,0表示没有鸟飞来,1表示来的是雄鸟,2表示来的是雌鸟。

输出:

每组数据输出一行只包含一个数,表示最多的鸟儿数量。

示例输入:

5
10 1
1212121212
10 3
1111122222
16 3
2221112222211111
2 1
22
5 4
11111

示例输出:

10
6
9
0
4

提示:

参考答案(内存最优[964]):

#include <stdio.h>
#include <stdbool.h>
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,wit,i,j;
        char tim[1001];
        int number[1001]= {0};
        int witbird1[1001]= {0};
        int basebird1=0,basebird2=0;
        int max=0;
        scanf("%d%d%s",&a,&wit,tim);
        for(i=0; i<a; ++i)
        {
            if(tim[i]=='1')
            {
                bool judge=true;
                for(j=i+1; j-i<=wit&&j<a; ++j)
                    if(tim[j]=='2'&&witbird1[j]!=1)
                    {
                        ++basebird1;
                        judge=false;
                        witbird1[j]=1;
                        break;
                    }
                if(judge)
                    for(j=i; j-i<wit&&j<a; ++j)
                        ++number[j];
            }
            else if(tim[i]=='2' && witbird1[i])
                ++basebird2;
            number[i]+=basebird1+basebird2;
            if(number[i]>max)max=number[i];
        }
        printf("%d\n",max);
    }
    return 0;
}

参考答案(时间最优[0]):

#include<stdio.h>
#include<stdlib.h>
#include<cmath>
#include<string.h>
#define N 1005

struct node
{
    int a,b;             //b用来记录这只鸟是否已配成对
}f[N];

int max(int a,int b)
{
    return a>b?a:b;
}
char str[N];
int main()
{
    int i,j,n,p,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&p);
        memset(f,0,sizeof(f));
        scanf("%s",str);
        for(i=0;i<n;i++)
            f[i].a=str[i]-'0';
        for(i=0;i<n;i++)
        {
            if(f[i].a==2)  //只有有雌鸟飞来时判断树上是否有落单的雄鸟
            {
                j=max(0,i-p);
                for(;j<i;j++)
                    if(f[j].a==1&&f[j].b!=-1)  //有的话直接配成对,否则直接飞走
                    {
                        f[j].b=-1;
                        f[i].b=-1;
                        break;
                    }
            }
        }
        int t=0,cnt=0,ans=0;
        for(i=0;i<n;i++)
        {
            cnt=0;
            if(f[i].b==-1)       //标记后的鸟直接加起来
                t++;
            if(i-p<0)
                j=0;
            else
                j=i-p+1;
            for(;j<=i;j++)        //查找当前树上落单雄鸟个数
                if(f[j].a==1&&f[j].b!=-1)
                    cnt++;
            ans=max(ans,t+cnt);
        }
        printf("%d\n",ans);
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注