人员排日程
时间: 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);
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。