POJ 1250 Tanning Salon（我的水題之路——字母表數組标記）

Tanning Salon

Time Limit: 1000MS	Memory Limit: 10000K
Total Submissions: 5475	Accepted: 2994

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.      

Source

Mid-Central USA 2002

題意是說，有一個沙龍，裡面有N個床，會有很多客人過來住，如果當一個客人過來，但是沙龍的床已經滿了，那麼這個客人就要離開。題目将給出床的數量N，和一個字元隊列，表示客人們來的順序。每個客人的均用一個字元表示，每個客人的字元會在隊列了出現了兩次，第一次表示客人到來，占用了一個床，第二次出現表示客人離開，将床位讓開。

解法是用一個字元數組對每個字元的狀态進行标記，如果這個人出現了，且床位有空，則讓其字元标記為1，請床位書fullnum加1，如果床位已滿，則讓字元數組标記為2，且離開人數量加一。如果這個人離開了，就讓fullnum減一，且該字母标記為0.将整個隊列标記一次之後就可以得到結果。

這個方法的适用于以下情況： 1）所有的字母僅出現一次 2）每個字母有多個狀态

代碼（1AC）：

#include <cstdio>
#include <cstdlib>
#include <cstring>

char array[50];
int words[50];
int N;

int main(void){
    int i, j;
    int len, leftnum;
    int fullnum;
    while (scanf("%d", &N) , N != 0){
        scanf(" %s", array);
        memset(words, 0, sizeof(words));
        len = strlen(array);
        leftnum = fullnum = 0;
        for (i = 0; i < len; i ++){
            if (words[array[i] - '0'] == 0){
                if (fullnum < N){
                    words[array[i] - '0'] = 1;
                    fullnum++;
                }
                else{
                    words[array[i] - '0'] = 2;
                    leftnum++;
                }
            }
            else if (words[array[i] - '0'] == 1){
                fullnum --;
                words[array[i] - '0'] = 0;
            }
            else if(words[array[i] - '0'] == 2){
                    words[array[i] - '0'] = 0;
            }
        }
        if (leftnum == 0){
            printf("All customers tanned successfully.\n");
        }
        else{
            printf("%d customer(s) walked away.\n", leftnum);
        }
    }
    return 0;
}