HDOJ 2160-母猪的故事【队列】

清疚 2022-08-21 04:41 134阅读 0赞

# 母猪的故事 #

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 8834 Accepted Submission(s): 5470

Problem Description

话说现在猪肉价格这么贵，著名的ACBoy 0068 也开始了养猪生活。说来也奇怪，他养的猪一出生第二天开始就能每天中午生一只小猪，而且生下来的竟然都是母猪。  
不过光生小猪也不行，0068采用了一个很奇特的办法来管理他的养猪场：  
对于每头刚出生的小猪，在他生下第二头小猪后立马被杀掉，卖到超市里。  
假设在创业的第一天，0068只买了一头刚出生的小猪，请问，在第N天晚上，0068的养猪场里还存有多少头猪？

Input

测试数据的第一行包含有一个正整数T，代表测试数据的个数。接下来有T组测试，每组测试数据占一行，分别有一个正整数N代表0068创业的第N天。(0<N<20)

Output

对于每组数据，请在一行里输出第N天晚上养猪场里猪的数目。

Sample Input

2
    2
    3

Sample Output

2
    3

Author

linle

Source

[2008信息工程学院集训队——选拔赛 ][2008_]

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<queue>
    using namespace std;
    int map[100000];
    int main()
    {
    	queue<int >q;
    	int T;
    	int i,j;
    	map[1]=1,map[2]=2;
    	q.push(2);
    	q.push(1);
    	for(i=3;i<=20;i++)
    	{
    		int wc=0;
    		while(q.front()!=3)
    		{
    			int yy=q.front();
    			q.pop();
    			yy++;
    			q.push(yy);
    			wc++;
    		}		
    		int yy=wc;
    		while(yy--)
    		{
    			q.push(1);
    		}
    		while(q.front()==3)
    		{
    			q.pop();
    		}
    		map[i]=q.size();
    	}
    	scanf("%d",&T);
    	while(T--)
    	{
    		int n;
    		scanf("%d",&n);
    		printf("%d\n",map[n]);
    	}
    	return 0;
    }

[2008_]: http://acm.hdu.edu.cn/search.php?field=problem&key=2008%D0%C5%CF%A2%B9%A4%B3%CC%D1%A7%D4%BA%BC%AF%D1%B5%B6%D3%A1%AA%A1%AA%D1%A1%B0%CE%C8%FC&source=1&searchmode=source