树上的鸟儿
Time Limit: 1000 ms Memory Limit: 65535 kB Solved: 43 Tried: 188
Submit
Status
Best Solution
Back
Description
作为电子科大的一员，大家都知道，我们校园有很多高大的银杏树，现在小明正在观察一棵树上的鸟儿，他发现了一些规律。
在这个树上，有一些雄鸟和雌鸟（小明很厉害，能分得出鸟儿的雄雌），假如来了一只雄鸟，它会在树上唱歌，如果p分钟内有一只雌鸟飞来和它一起唱，它们就会一直呆在树上不走了，否则p分钟之后，这只雄鸟就会飞走。假如来的是只雌鸟，如果没有落单的雄鸟在树上，它不会落到树上而是直接飞走，否则它会选择等待时间最长的雄鸟和它一起唱歌，就再也不走了。
现在小明记录了一段时间飞来这个银杏树的鸟儿，每隔一分钟可能会飞来一只雌鸟或雄鸟，或者什么都没有发生，现在小明想知道这段时间内树上最多有多少只鸟儿，你可以帮助他吗？
Input
首先输入一个正整数T，T <= 50，表示有T组数据。
每组第一行给出两个整数n、p，分别表示记录时间段的长度，和每个雄鸟最多能等待的时间（1 < n <= 1000,1 <= p <= 10）。
第二行为一个长度为n的字符串，由 0, 1, 2三种字符构成，表示这段时间内鸟儿飞来的情况，0表示没有鸟飞来，1表示来的是雄鸟，2表示来的是雌鸟。
Output
每组数据输出一行只包含一个数，表示最多的鸟儿数量。
Sample Input
5
10 1
1212121212
10 3
1111122222
16 3
2221112222211111
2 1
22
5 4
11111
Sample Output
10
6
9
0
4
Hint
如果在某个时刻，同时发生了鸟儿的飞进飞出，那么先有一只鸟儿飞出枝头，再由另一只鸟儿飞上枝头，参考第三组样例，第15只鸟飞上枝头的时候，第12只鸟已经离开了。第12只鸟离开的原因是因为第15只是雄鸟，如果第15只是雌鸟，第12只就不会飞走了。
思路：用结构体存储数据，首先遍历数组，把能配成对的鸟标记一下；
然后再次遍历数组，统计当前时刻一共有几只配成对的鸟，
再查找树上还有几只落单的雄鸟，更新最大值；
得出答案！！
#include
#include
#include
#include
#define N 1005
struct node
{
int a,b; //b用来记录这只鸟是否已配成对
}f[N];
char str[N];
int max(int a,int b)
{
return a>b a:b;
}
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
for(i=0;i
if(f[i].a==2) //只有有雌鸟飞来时判断树上是否有落单的雄鸟
{
for(j=max(0,i-p);j
{
f[j].b=-1;
f[i].b=-1;
break;
}
}
}
int t=0,cnt=0,ans=0;
for(i=0;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 ,ans);
}
return 0;
}