POJ 题目1250 Tanning Salon (链表应用)


Tanning Salon
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 6820   Accepted: 3686

Description

Tan Your Hide, Inc., owns several coin-operated tanning salons. Research has shown that if a customer arrives and there are no beds available, the customer will turn around and leave, thus costing the company a sale. Your task is to write a program that tells the company how many customers left without tanning. 

Input

The input consists of data for one or more salons, followed by a line containing the number 0 that signals the end of the input. Data for each salon is a single line containing a positive integer, representing the number of tanning beds in the salon, followed by a space, followed by a sequence of uppercase letters. Letters in the sequence occur in pairs. The first occurrence indicates the arrival of a customer, the second indicates the departure of that same customer. No letter will occur in more than one pair. Customers who leave without tanning always depart before customers who are currently tanning. There are at most 20 beds per salon. 

Output

For each salon, output a sentence telling how many customers, if any, walked away. Use the exact format shown below. 

Sample Input

2 ABBAJJKZKZ
3 GACCBDDBAGEE
3 GACCBGDDBAEE
1 ABCBCA
0

Sample Output

All customers tanned successfully.
1 customer(s) walked away.
All customers tanned successfully.
2 customer(s) walked away.






建立两个链表L,W,  L用来存放当前bed状态,W用来存放当前wait等待人数,

每当新到达一个新的客户,

首先判断新客户是否已在L中,如果在L中,将其从L删除,

如果不在L,再判断元素个数是否大于n,

如果L中元素个数小于n,则将新客户添加到L,

否则,判断新客户是否在W中,如果不在,则cnt++(等待人数++);如果在w中,则从w删除





#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

typedef struct node
{
	char elem;
	node * next;
}node;
typedef struct list
{
	node * head;
}list;
	
void Print(list L)
{
	node *p=L.head;
	while(p)
	{
		printf("%c",p->elem);
		p=p->next;
	}
//	printf("-----------\n");
}
int length(list L)
{
	node * p = L.head;
	int len = 0;
	while(p)
	{
		len++;
		p = p->next;
	} 
	return len;
	
}
void insert(list &L, char e)
{
	node * p;
	p = (node *)malloc(sizeof(node));
	p->elem = e;	
	p->next = L.head;
	L.head = p;	
	//Print(L);
}
void delet(list &L, char e)
{
	node * c;
//	Print(L);
	node * p = L.head;
	node * s=p;
	if(p->elem ==e)
	{
		L.head = p->next;
	}
	else
	{
		while( p->elem != e)
		{
			s = p;
			p = p->next;
		} 
		s->next = p->next;
	}
	
	free(p);
	
}
bool find(list L, char e)
{
	node * p = L.head; 
	while(p)
	{
		if( p->elem==e) 	return true;
		p=p->next;
	}
//	printf("meiyou\n");
	return false;
}

void init(list &L)
{
	L.head = (node *)malloc(sizeof(node));
	if(!L.head) exit(-1);
	L.head=NULL;
}

int main()
{
	int n,i;
	char s[1000];
	list L;
	list W;
	init(L); init(W);
	while(scanf("%d",&n),n)
	{
		scanf("%s",s);
	//	puts(s);
	//	printf("n=%d\n",n);
//   3 GACCBDDBAGEE
	
	//	printf("l=%c,len=%d\n",s[0],strlen(s));

	//	Print(L);
		int cnt = 0;

		for(i=0;i<strlen(s);i++)
		{
		//	printf("i=%c,len=%d\n",s[i],length(L));
			if(!find(L,s[i]))//对L来说新来客户
			{
				if(length(L)<n ){
					insert(L,s[i]);
			//		Print(L);
				 }
				else
				{	
				//	printf("###\n");
				//	Print(W);

					if(!find(W,s[i]))	
					{
						
						insert(W,s[i]);
						cnt ++;
					}
					else delet(W,s[i]);
				} 
				//Print(L);
			}
			else delet(L,s[i]);
			
		}
		if(cnt==0) printf("All customers tanned successfully.\n");
		else printf("%d customer(s) walked away.\n",cnt);
		
	}
	return 0;
}