【C++编程题】占座位

本文主要是介绍【C++编程题】占座位，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

【问题描述】sun所在学校的教室座位每天都是可以预占的。
一个人可以去占多个座位，而且一定是要连续的座位，如果占不到他所要求的这么多座位，那么他就一个座位也不要了。为了降低难度，每次分配座位按座位号从小到大查找，采用最先适配法分配座位。

【输入形式】输入有多组数据。
每组数据输入座位排数n，0<n<=100（座位的排列数相等，座位是按每行从左到右依次排序的, 第1行的最右边一个座位与第二行的第一个座位视为连续座位），m（ 0<m<=min(100,n*n) ）个人。
然后输入k（0<k<=100），最后输入k个命令。
命令只有两种：
1.in id num（代表id,0<=id<m,要占num个座位，若占不到连续的num(0<num<=20)个座位表示该命令无效）
2.out id（代表id要释放他之前占的所有座位）
注意：如果id之前占过座还没释放那么之后他的in命令都是无效的，
如果id之前没占过座位那么他的out命令也是无效的。

【输出形式】对每个in命令输出yes或者no，如果命令有效则输出yes，无效则输出no。
在yes no后面只带有回车，不带其他任何字符。

【样例输入】

4 10

9

in 1 7

in 2 3

in 3 3

in 3 3

in 4 3

out 2

in 5 6

out 3

in 5 6

【样例输出】

yes
yes

yes

no

yes

yes

no

yes

yes

【思路】

把二维的位置转为一维数组储存，把【座位】和【人】的信息储存好就成功一大步了~

【AC代码】

 #include<iostream>
 #include<vector>
 #include<string>
 #include<stack> 
 #include<cmath>
 #include<algorithm>
 #include<set>
 #include<cstring>
 #include<iomanip> 
 #include<sstream>
 #include<map>
 using namespace std;
 
 struct person{
 	int is;   //是否占座，同时记录占了多少个座位
	int st;   //占座开始位置
 	int ed;   //占座结束位置
 	
 	person(){
 		is=0;
 		st=0;
 		ed=0;
	 }
	 
	void init(){  //当释放座位时，清零
		is=0;
 		st=0;
 		ed=0;
	}
 }p[10010];
 
 int sit[10010];   //座位连续，因此把直接用一维数组储存位置信息
 
 int main(){
 	int n;
 	cin>>n;  //座位数n*n
	n=n*n; 
 	
 	int m;
 	cin>>m;   //编号0~m-1的人   他的编号id同时也是person的下标
 	
 	memset(sit,-1,sizeof(sit));  //初始化数组为-1  表示没人坐过 （编号0开始，防止冲突）
 	
 	int t;
 	cin>>t;
 	while(t--){
 		string s;
 		cin>>s;
 		
 		if(s=="in"){
 			int id,num;
 			cin>>id>>num;
 			
 			if(p[id].is != 0){      //已经占了座位 不能再占
 				cout<<"no"<<'\n';
 				continue;
			 }
			 	 
			int flag=0;
			for(int k=1;k<=n;k++){
				while(sit[k]!=-1 && k<=n) k++;  //找到第一个为-1的空座位
					
				if(k>n) break;    //找不到空座位
				
				int maxi=0;
				int st=k;	
				while(sit[st]==-1 && st<=n)  {   //连续最大空座位
					maxi++;
					st++;         //用while别忘了步数增加啊啊啊
				}
				
				 if(maxi>=num){        //位置足够
				 	p[id].is = num;
				 	p[id].st = k;
				 	p[id].ed = k + num -1;
				 	
				 	for(int i=k;i<=k+num-1;i++){  //更新位置信息 
				 		sit[i]=id;
					 }
					 
					 flag=1;
					 cout<<"yes"<<'\n'; 
					 break;
				 }
			} 
 			if(flag==0 )  cout<<"no"<<'\n'; //最大连续空座位不足以占座
		 }
		 
 		else if(s=="out"){
 			int id;
 			cin>>id;
 			
 			if(p[id].is == 0){   //本身无座位 
 				cout<<"no"<<'\n';
 				continue;
			 } 
			 
			 for(int i=p[id].st ; i<=p[id].ed ;i++){  清空座位
			 	sit[i]=-1;	
			 } 
			 
			p[id].init() ;			
			cout<<"yes"<<'\n';
		 }			
	 }	
 }

【写在后面】

觉得对你有帮助的话记得一键三连哦~（误

相关题目放在了【HNU CJ】专栏

如果有啥问题可以评论留言或者私我哦~

这篇关于【C++编程题】占座位的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！