人员排日程

人员排日程

时间: 1ms        内存:128M

描述:

    某保密单位机要人员 A,B,C,D,E 每周需要工作5天,休息2天。

    上级要求每个人每周的工作日和休息日安排必须是固定的,不能在周间变更。

    此外,由于工作需要,还有如下要求:

    1. 所有人的连续工作日不能多于3天(注意:周日连到下周一也是连续)。

    2. 一周中,至少有3天所有人都是上班的。

    3. 任何一天,必须保证 A B C D 中至少有2人上班。

    4. B D E 在周日那天必须休息。

    5. A E 周三必须上班。

    6. A C 一周中必须至少有4天能见面(即同时上班)。

    你的任务是:编写程序,列出ABCDE所有可能的一周排班情况。工作日记为1,休息日记为0
   
    A B C D E 每人占用1行记录,从星期一开始。

输入:

输出:

    程序没有输入,要求输出所有可能的方案。

    每个方案是7x5的矩阵。只有1和0组成。       
   
    矩阵中的列表示星期几,从星期一开始。

    矩阵的行分别表示A,B,C,D,E的作息时间表。

    多个矩阵间用空行分隔开。

示例输入:

示例输出:


0110111
1101110
0110111
1101110
1110110

提示:

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

#include <iostream>
#include <cmath>
#define A0 (A&POW(2,0))
#define A1 (A&POW(2,1))
#define A2 (A&POW(2,2))
#define A3 (A&POW(2,3))
#define A4 (A&POW(2,4))
#define A5 (A&POW(2,5))
#define A6 (A&POW(2,6))
#define B0 (B&POW(2,0))
#define B1 (B&POW(2,1))
#define B2 (B&POW(2,2))
#define B3 (B&POW(2,3))
#define B4 (B&POW(2,4))
#define B5 (B&POW(2,5))
#define B6 (B&POW(2,6))
#define C0 (C&POW(2,0))
#define C1 (C&POW(2,1))
#define C2 (C&POW(2,2))
#define C3 (C&POW(2,3))
#define C4 (C&POW(2,4))
#define C5 (C&POW(2,5))
#define C6 (C&POW(2,6))
#define D0 (D&POW(2,0))
#define D1 (D&POW(2,1))
#define D2 (D&POW(2,2))
#define D3 (D&POW(2,3))
#define D4 (D&POW(2,4))
#define D5 (D&POW(2,5))
#define D6 (D&POW(2,6))
#define E0 (E&POW(2,0))
#define E1 (E&POW(2,1))
#define E2 (E&POW(2,2))
#define E3 (E&POW(2,3))
#define E4 (E&POW(2,4))
#define E5 (E&POW(2,5))
#define E6 (E&POW(2,6))
using namespace std;
int main()
{	
	int POW(int,int);
	int A,B,C,D,E;
	bool have=false;
	int count;
	int T=0;
	int test;
	int i;
	bool chao;
					cout<<endl;
	for(A=pow(2,7)-1;A>=0;A--)
	{	
			if(!A2)continue;
			chao=false;
			test=A;
			count=0;
			for(i=0;i<7;i++)
			{	
				if(test&1)
				{
					count++;
					if(count==4)
					{
						chao=true;
						break;
					}
				}
				else
				{
					count=0;
				}
				test>>=1;
			}
			if(chao)continue;
			else
			{
				if(count!=0)
				{	
					test=A;
					for(i=0;i<3;i++)
					{
						if(test&1)count++;
						else count=0;
					}
					if(count>=4)chao=true;
				}
				if(chao)continue;
			}
			for(B=pow(2,6)-1;B>=0;B--)
	{		
			chao=false;
			test=B;
			count=0;
			for(i=0;i<7;i++)
			{	
				if(test&1)
				{
					count++;
					if(count==4)
					{
						chao=true;
						break;
					}
				}
				else
				{
					count=0;
				}
				test>>=1;
			}
			if(chao)continue;
			else
			{
				if(count!=0)
				{	
					test=B;
					for(i=0;i<3;i++)
					{
						if(test&1)count++;
						else count=0;
					}
					if(count>=4)chao=true;
				}
				if(chao)continue;
			}
			for(C=pow(2,7)-1;C>=0;C--)
	{		
			chao=false;
			count=0;
			test=A&C;
			while(test)
			{
				count+=((test&1)>0);
				test>>=1;
			}
			if(count<4)continue;
			test=C;
			count=0;
			for(i=0;i<7;i++)
			{	
				if(test&1)
				{
					count++;
					if(count==4)
					{
						chao=true;
						break;
					}
				}
				else
				{
					count=0;
				}
				test>>=1;
			}
			if(chao)continue;
			else
			{
				if(count!=0)
				{	
					test=C;
					for(i=0;i<3;i++)
					{
						if(test&1)count++;
						else count=0;
					}
					if(count>=4)chao=true;
				}
				if(chao)continue;
			}
			for(D=pow(2,6)-1;D>=0;D--)
	{	
			chao=false;
			if((A1>0)+(B1>0)+(C1>0)+(D1>0)<2)continue;
			if((A2>0)+(B2>0)+(C2>0)+(D2>0)<2)continue;
			if((A3>0)+(B3>0)+(C3>0)+(D3>0)<2)continue;
			if((A4>0)+(B4>0)+(C4>0)+(D4>0)<2)continue;
			if((A5>0)+(B5>0)+(C5>0)+(D5>0)<2)continue;
			if((A6>0)+(B6>0)+(C6>0)+(D6>0)<2)continue;
			if((A0>0)+(B0>0)+(C0>0)+(D0>0)<2)continue;
			test=D;
			count=0;
			for(i=0;i<7;i++)
			{	
				if(test&1)
				{
					count++;
					if(count==4)
					{
						chao=true;
						break;
					}
				}
				else
				{
					count=0;
				}
				test>>=1;
			}
			if(chao)continue;
			else
			{
				if(count!=0)
				{	
					test=D;
					for(i=0;i<3;i++)
					{
						if(test&1)count++;
						else count=0;
					}
					if(count>=4)chao=true;
				}
				if(chao)continue;
			}

			for(E=pow(2,6)-1;E>=0;E--)
	{	
			chao=false;
			if(!E2)continue;
			test=A&B&C&D&E;
			count=0;
			while(test)
			{	
				count+=((test&1)>0);
				test>>=1;
			}
			if(count<3)continue;
			test=E;
			count=0;
			for(i=0;i<7;i++)
			{	
				if(test&1)
				{
					count++;
					if(count==4)
					{
						chao=true;
						break;
					}
				}
				else
				{
					count=0;
				}
				test>>=1;
			}
			if(chao)continue;
			else
			{
				if(count!=0)
				{	
					test=E;
					for(i=0;i<3;i++)
					{
						if(test&1)count++;
						else count=0;
					}
					if(count>=4)chao=true;
				}
				if(chao)continue;
			}
			T++;
			test=A;
			for(i=0;i<7;i++)
			{
				cout<<(test&1);
				test>>=1;
			}
			cout<<endl;
			test=B;
			for(i=0;i<7;i++)
			{
				cout<<(test&1);
				test>>=1;
			}
			cout<<endl;
			test=C;
			for(i=0;i<7;i++)
			{
				cout<<(test&1);
				test>>=1;
			}
			cout<<endl;
			test=D;
			for(i=0;i<7;i++)
			{
				cout<<(test&1);
				test>>=1;
			}
			cout<<endl;
			test=E;
			for(i=0;i<7;i++)
			{
				cout<<(test&1);
				test>>=1;
			}
			cout<<endl;
			have=true;
			if(have)break;
			if(T!=8)cout<<endl;
	}
			if(have)break;
	}
			if(have)break;
	}
			if(have)break;
	}
			if(have)break;
	}
	return 0;
}
int POW(int d,int n)
{
	return pow(d,n);
}

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

#include <iostream>
#include <cmath>
#define A0 (A&POW(2,0))
#define A1 (A&POW(2,1))
#define A2 (A&POW(2,2))
#define A3 (A&POW(2,3))
#define A4 (A&POW(2,4))
#define A5 (A&POW(2,5))
#define A6 (A&POW(2,6))
#define B0 (B&POW(2,0))
#define B1 (B&POW(2,1))
#define B2 (B&POW(2,2))
#define B3 (B&POW(2,3))
#define B4 (B&POW(2,4))
#define B5 (B&POW(2,5))
#define B6 (B&POW(2,6))
#define C0 (C&POW(2,0))
#define C1 (C&POW(2,1))
#define C2 (C&POW(2,2))
#define C3 (C&POW(2,3))
#define C4 (C&POW(2,4))
#define C5 (C&POW(2,5))
#define C6 (C&POW(2,6))
#define D0 (D&POW(2,0))
#define D1 (D&POW(2,1))
#define D2 (D&POW(2,2))
#define D3 (D&POW(2,3))
#define D4 (D&POW(2,4))
#define D5 (D&POW(2,5))
#define D6 (D&POW(2,6))
#define E0 (E&POW(2,0))
#define E1 (E&POW(2,1))
#define E2 (E&POW(2,2))
#define E3 (E&POW(2,3))
#define E4 (E&POW(2,4))
#define E5 (E&POW(2,5))
#define E6 (E&POW(2,6))
using namespace std;
int main()
{	
	int POW(int,int);
	int A,B,C,D,E;
	bool have=false;
	int count;
	int T=0;
	int test;
	int i;
	bool chao;
					cout<<endl;
	for(A=pow(2,7)-1;A>=0;A--)
	{	
			if(!A2)continue;
			chao=false;
			test=A;
			count=0;
			for(i=0;i<7;i++)
			{	
				if(test&1)
				{
					count++;
					if(count==4)
					{
						chao=true;
						break;
					}
				}
				else
				{
					count=0;
				}
				test>>=1;
			}
			if(chao)continue;
			else
			{
				if(count!=0)
				{	
					test=A;
					for(i=0;i<3;i++)
					{
						if(test&1)count++;
						else count=0;
					}
					if(count>=4)chao=true;
				}
				if(chao)continue;
			}
			for(B=pow(2,6)-1;B>=0;B--)
	{		
			chao=false;
			test=B;
			count=0;
			for(i=0;i<7;i++)
			{	
				if(test&1)
				{
					count++;
					if(count==4)
					{
						chao=true;
						break;
					}
				}
				else
				{
					count=0;
				}
				test>>=1;
			}
			if(chao)continue;
			else
			{
				if(count!=0)
				{	
					test=B;
					for(i=0;i<3;i++)
					{
						if(test&1)count++;
						else count=0;
					}
					if(count>=4)chao=true;
				}
				if(chao)continue;
			}
			for(C=pow(2,7)-1;C>=0;C--)
	{		
			chao=false;
			count=0;
			test=A&C;
			while(test)
			{
				count+=((test&1)>0);
				test>>=1;
			}
			if(count<4)continue;
			test=C;
			count=0;
			for(i=0;i<7;i++)
			{	
				if(test&1)
				{
					count++;
					if(count==4)
					{
						chao=true;
						break;
					}
				}
				else
				{
					count=0;
				}
				test>>=1;
			}
			if(chao)continue;
			else
			{
				if(count!=0)
				{	
					test=C;
					for(i=0;i<3;i++)
					{
						if(test&1)count++;
						else count=0;
					}
					if(count>=4)chao=true;
				}
				if(chao)continue;
			}
			for(D=pow(2,6)-1;D>=0;D--)
	{	
			chao=false;
			if((A1>0)+(B1>0)+(C1>0)+(D1>0)<2)continue;
			if((A2>0)+(B2>0)+(C2>0)+(D2>0)<2)continue;
			if((A3>0)+(B3>0)+(C3>0)+(D3>0)<2)continue;
			if((A4>0)+(B4>0)+(C4>0)+(D4>0)<2)continue;
			if((A5>0)+(B5>0)+(C5>0)+(D5>0)<2)continue;
			if((A6>0)+(B6>0)+(C6>0)+(D6>0)<2)continue;
			if((A0>0)+(B0>0)+(C0>0)+(D0>0)<2)continue;
			test=D;
			count=0;
			for(i=0;i<7;i++)
			{	
				if(test&1)
				{
					count++;
					if(count==4)
					{
						chao=true;
						break;
					}
				}
				else
				{
					count=0;
				}
				test>>=1;
			}
			if(chao)continue;
			else
			{
				if(count!=0)
				{	
					test=D;
					for(i=0;i<3;i++)
					{
						if(test&1)count++;
						else count=0;
					}
					if(count>=4)chao=true;
				}
				if(chao)continue;
			}

			for(E=pow(2,6)-1;E>=0;E--)
	{	
			chao=false;
			if(!E2)continue;
			test=A&B&C&D&E;
			count=0;
			while(test)
			{	
				count+=((test&1)>0);
				test>>=1;
			}
			if(count<3)continue;
			test=E;
			count=0;
			for(i=0;i<7;i++)
			{	
				if(test&1)
				{
					count++;
					if(count==4)
					{
						chao=true;
						break;
					}
				}
				else
				{
					count=0;
				}
				test>>=1;
			}
			if(chao)continue;
			else
			{
				if(count!=0)
				{	
					test=E;
					for(i=0;i<3;i++)
					{
						if(test&1)count++;
						else count=0;
					}
					if(count>=4)chao=true;
				}
				if(chao)continue;
			}
			T++;
			test=A;
			for(i=0;i<7;i++)
			{
				cout<<(test&1);
				test>>=1;
			}
			cout<<endl;
			test=B;
			for(i=0;i<7;i++)
			{
				cout<<(test&1);
				test>>=1;
			}
			cout<<endl;
			test=C;
			for(i=0;i<7;i++)
			{
				cout<<(test&1);
				test>>=1;
			}
			cout<<endl;
			test=D;
			for(i=0;i<7;i++)
			{
				cout<<(test&1);
				test>>=1;
			}
			cout<<endl;
			test=E;
			for(i=0;i<7;i++)
			{
				cout<<(test&1);
				test>>=1;
			}
			cout<<endl;
			have=true;
			if(have)break;
			if(T!=8)cout<<endl;
	}
			if(have)break;
	}
			if(have)break;
	}
			if(have)break;
	}
			if(have)break;
	}
	return 0;
}
int POW(int d,int n)
{
	return pow(d,n);
}

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

点赞

发表评论

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