[数据结构与算法]数据结构与算法复习：第三十四弹

1. 知识点总结

知识点：模拟、栈和链表

2. 分题题解

2.1 1026 Table Tennis

emmm需要回头重新写的题目，写了一上午，突破时间和代码量双重禁制……

喜提19/30

代码如下：

#include<bits/stdc++.h>
using namespace std;
/*
对于普通/VIP用户而言，每次选择可以用的桌子当中，id最小的
VIP特殊点在于，当VIP桌子可以用的时候，可以插队 
*/ 
const int OPEN_TIME=8*3600;
const int CLOSE_TIME=21*3600;
struct People{
	int id; 
	int arrive;//到达的时间
	int serve;//服务时长
};
int N,M,K;
int hh,mm,ss,s,vip;
vector<People>cp,vp;//普通人，VIP
int clen=0,vlen=0;
int cid=0,vid=0;
People p,people; 
bool cmp_arrive(People a,People b){
	return a.arrive<b.arrive;
}
//关于桌子
vector<bool>isVip;
struct Table{
	int id;
	int take_in=OPEN_TIME;
	bool operator <(Table table)const{
		if(this->take_in!=table.take_in){
			return this->take_in>table.take_in;
		}else{
			return this->id > table.id;
		}
	} 
}; 
priority_queue<Table>ct_q,vt_q;
Table table;
//关于答案
struct People_ans{
	int arrive;
	int start_serve;
	int wait;
	int available=0;//是否算数 
}; 
vector<People_ans>pans;
vector<int>cnts;//计算每张桌子的使用次数 
bool cmp_ans(People_ans a,People_ans b){
	if(a.available!=b.available){
		return a.available>b.available;
	}else{
		return a.start_serve<b.start_serve;
	}
}
void getTablePeople(){
	//先选人 :选择先来的 
	bool isVip=false;
	if(vid<vlen){
		if(cid<clen){
			if(cp[cid].arrive<vp[vid].arrive){
				people=cp[cid];
				cid++;
			}else{
				people=vp[vid];
				vid++;
				isVip=true;
			}
		}else{
			people=vp[vid];
			vid++;
			isVip=true;
		}
	}else{
		people=cp[cid];
		cid++;
	} 
	//再选桌子
	if(vt_q.top().take_in<=people.arrive){
		if(ct_q.top().take_in<=people.arrive){
			//两张桌子都可以用 且没有VIP
			while(vt_q.top().take_in<people.arrive){
				table=vt_q.top();
				vt_q.pop();
				table.take_in=people.arrive;
				vt_q.push(table);
			}
			while(ct_q.top().take_in<people.arrive){
				table=ct_q.top();
				ct_q.pop();
				table.take_in=people.arrive;
				ct_q.push(table);
			}
			if(vt_q.top().id<ct_q.top().id){
				table=vt_q.top();
				vt_q.pop();
			}else{
				table=ct_q.top();
				ct_q.pop(); 
			}
		}else{
			//只有VIP的桌子可以用
			table=vt_q.top();
			vt_q.pop();
		}
	}else{
		if(ct_q.top().take_in<=people.arrive){
			//只有普通桌子可以用 
			table=ct_q.top();
			ct_q.pop(); 
		}else{
			//都不可以用-等属于自己的 
			if(isVip){
				table=vt_q.top();
				vt_q.pop();
			}else{
				table=ct_q.top();
				ct_q.pop(); 
			} 
		}
	}
}
int main(){
	scanf("%d",&N);
	pans.resize(N);
	for(int i=0;i<N;i++){
		scanf("%d:%d:%d %d %d",&hh,&mm,&ss,&s,&vip);
		p.arrive=hh*3600+mm*60+ss;
		if(s>120){
			s=120;
		}
		p.serve=s*60;//按秒计数
		p.id=i;
		pans[i].arrive=p.arrive; 
		if(vip){
			vp.push_back(p);
			vlen++;
		}else{
			cp.push_back(p);
			clen++;
		}
	} 
	scanf("%d%d",&K,&M);
	isVip.resize(K+1,false);
	cnts.resize(K+1,0);
	for(int i=0;i<M;i++){
		scanf("%d",&vip);
		isVip[vip]=true;
	}
	for(int i=1;i<=K;i++){
		table.id=i;
		if(isVip[i]){
			vt_q.push(table);
		}else{
			ct_q.push(table);
		}
	}
	sort(vp.begin(),vp.end(),cmp_arrive);
	sort(cp.begin(),cp.end(),cmp_arrive); 
	while(cid<clen||vid<vlen){
		//首先选择当前的桌子 
		//在什么情况下可以VIP抢座
		if(vid<vlen&&vp[vid].arrive<=vt_q.top().take_in&&vt_q.top().take_in<=CLOSE_TIME){
			table=vt_q.top();
			vt_q.pop();
			people=vp[vid];
			vid++;
		}else{
			getTablePeople(); 
		}
		int start_serve=max(table.take_in,people.arrive);//开始服务的时间 
		int leave=start_serve+people.serve;//离开的时间 
		pans[people.id].start_serve=start_serve;//人接受服务的时间 
		pans[people.id].wait=start_serve-people.arrive;//人等待的时间  
		table.take_in=leave;
		if(start_serve<=CLOSE_TIME){
			cnts[table.id]++;
			pans[people.id].available=1;
		}
		if(isVip[table.id]){
			vt_q.push(table);
		}else{
			ct_q.push(table);
		}
		//刷新 
		int min_t=min(vt_q.top().take_in,ct_q.top().take_in);
		for(int i=vid;i<vlen;i++){
			if(vp[i].arrive<min_t){
				vp[i].arrive=min_t;
			}else{
				break;
			}
		}
		for(int i=cid;i<clen;i++){
			if(cp[i].arrive<min_t){
				cp[i].arrive=min_t;
			}else{
				break;
			}
		}
	}
	sort(pans.begin(),pans.end(),cmp_ans); 
	//输出答案 
	for(int i=0;i<N;i++){
		if(pans[i].available==0){
			break;
		}else{
			printf("%02d:%02d:%02d ",pans[i].arrive/3600,(pans[i].arrive-pans[i].arrive/3600*3600)/60,pans[i].arrive%60);
			printf("%02d:%02d:%02d ",pans[i].start_serve/3600,(pans[i].start_serve-pans[i].start_serve/3600*3600)/60,pans[i].start_serve%60);
			mm=(pans[i].start_serve-pans[i].arrive)/60;
			if((pans[i].start_serve-pans[i].arrive)%60>=30){
				mm++;
			}
			printf("%d\n",mm);
		}
	}
	for(int i=1;i<=K;i++){
		if(i-1){
			printf(" ");
		}
		printf("%d",cnts[i]);
	} 
	printf("\n");
	return 0;
}

看到一篇比较好的题解，但是今天的时间消耗完了，等之后有空补上⑧

【AC题解】

2.2 1051 Pop Sequence

就是根据给定的序列模拟出栈的过程，如果遇到不合法的出栈则标记为false退出

#include<bits/stdc++.h>
using namespace std;
int M,N,K,num;
vector<int>v;
int main(){
	scanf("%d%d%d",&M,&N,&K);
	v.resize(N);
	while(K--){
		stack<int>st;
		bool flag=true;
		for(int i=0;i<N;i++){
			scanf("%d",&v[i]);
		}
		//如何判断一个序列是否是指定大小的stack输出的序列 
		int id=0;
		int len=0;
		for(int i=1;i<=N;i++){
			while(!st.empty()&&id<N&&st.top()==v[id]){
				id++;
				len--;
				st.pop();
			}
			st.push(i);
			len++;
			if(len>M){
				flag=false;
			}
		}
		if(flag){
			while(id<N){
				if(st.top()==v[id]){
					id++;
					st.pop();
				}else{
					flag=false;
					break;
				}
			}
		}
		if(flag){
			printf("YES");
		}else{
			printf("NO");
		}
		if(K){
			printf("\n");
		}
	}
	return 0;
} 

2.3 1052 Linked List Sorting

这题没啥好说的，纯纯的链表题

#include<bits/stdc++.h>
using namespace std;
int head,N; 
struct Node{
	int val;
	int addr;
	int nxt;
};
vector<Node>nodes;
Node temp;
map<int,Node>mp;
bool cmp(Node a,Node b){
	return a.val<b.val;
}
int main(){
	scanf("%d%d",&N,&head);
	for(int i=0;i<N;i++){
		scanf("%d%d%d",&temp.addr,&temp.val,&temp.nxt);
		mp[temp.addr]=temp;
	}
	while(head!=-1){
		nodes.push_back(mp[head]);
		head=mp[head].nxt;
	}
	sort(nodes.begin(),nodes.end(),cmp);
	int len=nodes.size();
	if(len==0){
		printf("0 -1");
	}else{
		printf("%d %05d\n",len,nodes[0].addr);
	for(int i=0;i<len;i++){
		if(i){
			printf(" %05d\n",nodes[i].addr);
		}
		printf("%05d %d",nodes[i].addr,nodes[i].val);
	}
	printf(" -1");
	}
	return 0;
}