250
技术社区[云栖]
poj 1250 Tanning Salon
这题不用完全模拟不好做，我放弃用逻辑分析的方法。。
题意：一个旅馆有n个位，给出所有旅客到达旅馆和离开旅馆的顺序，问有多少旅客是没有住旅馆就离开的。
思路：基础模拟题。这句“Customers who leave without tanning always depart before customers who are currently tanning”要注意下，其实就是如果顾客i来的时候没有空位了，无论他什么时候离开，都是算做没有住旅馆。
其实我第一眼看这题的时候觉得应该用一个栈（广义栈），因为可以从任何位置离开。。后来发现这样想多了
其实这道题我开始并没有直接用一个Flag字符数组模拟床位，而是分析床位的count这样就有很多麻烦【见下面错误的代码】，比如一个顾客来了没有床位，但是他没有马上离开。。。又来了一个。。。
后来用完全模拟就直接过了。。。
AC的代码：
#include <stdio.h>
#include <string.h>
int main()
{
int n;
char Customers[100];
char bedFlag[25];
while(scanf("%d",&n)) //n 代表床位数量
{
//输入数据
if(n==0)
return 0;
scanf("%s",Customers);
memset(bedFlag,'#',sizeof(bedFlag)); //'#' 代表空位
//处理开始
int i,j,k;
int leaveNum=0;
for(i=0;i<strlen(Customers);i++)
{
//找床位，看在不在床位里
for(j=0;j<n;j++)
{
if(Customers[i]==bedFlag[j])
{
bedFlag[j]='#'; //收回床位
break;
}
}
if(j<n) //用完了离开的
continue;
else //不在床位中的
{
//看能找到空位吗
for(k=0;k<n;k++)
{
if(bedFlag[k]=='#')
{
bedFlag[k]=Customers[i];
break;
}
}
if(k<n) //找到空位
continue;
else
{
leaveNum++;
continue;
}
}
}
if(leaveNum==0)
printf("All customers tanned successfully.\n");
else
printf("%d customer(s) walked away.\n",leaveNum/2);
}
return 0;
}
错误的分析代码：
#include <stdio.h>
#include <string.h>
int main()
{
int n;
char Customers[100];
while(scanf("%d",&n)) //n 代表床位数量
{
//输入数据
if(n==0)
return 0;
scanf("%s",Customers);
//处理开始
int i,j;
int leaveNum=0;
int bedCount=0; //计数床数是否到达最大数量
for(i=0;i<strlen(Customers);i++)
{
//看之前出现过吗，出现过就代表leave，没有出现过就入床位
for(j=0;j<i;j++)
{
if(Customers[i]==Customers[j]) //以前出现过，代表离开，因为No letter will occur in more than one pair.
{
bedCount--;
break;
}
}
if(j<i) //用完床位，离开
continue;
else if(j==i) //新入来访
{
//看当前床位满了吗，满了就必须离开
if(bedCount==n)
{
leaveNum++;
i++;
continue;
}
else
bedCount++;
}
}
if(leaveNum==0)
printf("All customers tanned successfully.\n");
else
printf("%d\n",leaveNum);
}
return 0;
}
最后更新：2017-04-03 14:53:55