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