poj 1055 BULK MAILING-技术圈

BULK MAILING

Description

An organization that wishes to make a large mailing can save postage by following U.S. Postal Service rules for a bulk mailing. Letters in zip code order are bundled into packets of 10-15 letters each. Bundles may consist of letters in which all 5 digits of zip code are the same (5-digit bundles), or they may consist of letters in which only the first 3 digits of zip code are the same (3-digit bundles). If there are fewer than 10 letters to make up a bundle of either type, those letters are mailed first class.

Input

You are to write a program to read a data set of 5-digit zip codes, one per line, until end of input. Your program should count the number of 5-digit bundles, 3-digit bundles, and first class letters. You should include as many letters as possible in 5-digit bundles first, then as many as possible in 3-digit bundles, with as few bundles of 10 to 15 letters as possible. For example, if there are 31 letters with the same zip code, they must be combined into exactly three 5-digit bundles.
Not all zip codes in the data set will be valid. A valid zip code consists of exactly 5 digits (0-9), all of which cannot be 0. Non-numeric characters are not allowed. At the end of your output, print the invalid zip codes found. (Duplicates need only be printed once.)

Output

Print a report that lists 5-digit zip code bundles first, with the number of letters and number of bundles for each zip code. Next list all 3-digit zip code bundles with the same two counts, followed
by all zip codes that are not bundled and to be sent first class. At the end print totals of letters and bundles, followed by the number of invalid zip codes and a list of these. Single space the report, and print blank lines following the heading, before the total line, and between the three groups of zip codes. For 3-digit bundles, print the zip codes in the form dddxx, where ddd represents the three significant digits and xx represents the last two digits to be omitted. Your output should be similar to that shown in the sample.

Sample Input

Sample Output

ZIP         LETTERS     BUNDLES

95819          11           1
95864          10           1

958xx          25           2

95616           2           0
95747           1           0
95920           1           0

TOTALS         50           4

INVALID ZIP CODES

9j876
8976
00000
123456

Hint

you can copy the sample output to notpad,then you can see the real format of output.

批量邮寄

描述

希望进行大量邮寄的组织可以通过遵循美国邮政服务的批量邮寄规则来节省邮资。邮政编码顺序的信件被捆绑成每包 10-15 个字母的数据包。包裹可能由邮政编码的所有 5 位数字都相同的字母组成（5 位数字包裹），或者它们可能由邮政编码的前 3 位数字相同的字母组成（3 位数字包裹）。如果构成任一类型的一捆信件少于 10 封信件，则将这些信件邮寄至头等舱。

输入

您将编写一个程序来读取 5 位邮政编码的数据集，每行一个，直到输入结束。您的程序应该计算 5 位数据包、3 位数据包和一等信件的数量。您应该首先在 5 位数字包中包含尽可能多的字母，然后在 3 位数字包中包含尽可能多的字母，并且尽可能少地包含 10 到 15 个字母。例如，如果有 31 个字母具有相同的邮政编码，则它们必须组合成恰好三个 5 位数字的包。
并非数据集中的所有邮政编码都有效。有效的邮政编码由 5 位数字 (0-9) 组成，所有数字不能为 0。不允许使用非数字字符。在输出的末尾，打印找到的无效邮政编码。（副本只需要打印一次。）

输出

打印一份报告，首先列出 5 位邮政编码的包裹，以及每个邮政编码的字母数量和包裹数量。接下来列出具有相同两个计数的所有 3 位邮政编码捆绑包，然后
是所有未捆绑并优先发送的邮政编码。最后打印信件和包裹的总数，然后是无效邮政编码的数量和这些的列表。将报告单空格，并在标题后、总行前和三组邮政编码之间打印空行。对于 3 位数的包裹，以 dddxx 的形式打印邮政编码，其中 ddd 表示三位有效数字，xx 表示要省略的最后两位数字。您的输出应该类似于示例中显示的输出。

Sample Input

Sample Output

ZIP         LETTERS     BUNDLES

95819          11           1
95864          10           1

958xx          25           2

95616           2           0
95747           1           0
95920           1           0

TOTALS         50           4

INVALID ZIP CODES

9j876
8976
00000
123456

暗示

您可以将示例输出复制到记事本，然后您就可以看到输出的真实格式。

题目大意：

　　每封信都有一个zip-code, 由5位数字构成，可以通过将zip-code相同或相近的信件打包来节省成本。打包规则是：5位数字完全相同的10-15封可组成一个包(5-digit bundles)，或者将前3位数字相同的信件打包，同样10-15份一包(3-digit bundles)。优先分配为5-digit bundles，其次3-digit bundles。不能被打包的信件为first class letters。要求输出打包方案。

输入：没行一个zip-code，但并非每个都是合法的。合法的zip-code恰好由5位数字组成，不能全为0.

输出：按上述要求输出打包方案，格式见输出，合法的bundles和letters需要按数字大小顺序输出。

代码：

#include 
#include 
using namespace std;

struct Bundle { 
    int letter_cnt, bun_cnt; 
};

Bundle buns[100000];
char buffer[10], invalid_record[100000][10];
int invalid_cnt, zip_cnt[100000], total_letters, total_buns;

bool M[100000];

bool validity_check(char buffer[]){
    
    //位数检查
    if (strlen(buffer) != 5) {
        return false;
    }

    //数字检查
    for (int i = 0; i < 5; i++) {
        if (buffer[i] < '0' || buffer[i] > '9') {
            return false;
        }
    }

    //全0检查
    bool flag = true;
    for (int i = 0; i < 5; ++i) {
        if (buffer[i] != '0') {
            flag = false;
            break;
        }
    }
    if (flag) {
        return false;
    }
    return true;
}

void process1(void) {

    //同5位10份以上打包
    for (int i = 10000; i <= 99999; ++i) {
        if (zip_cnt[i] >= 10){
            while (zip_cnt[i] >= 15) {
                buns[i].letter_cnt += 15;
                ++buns[i].bun_cnt;
                total_letters += 15;
                ++total_buns;
                zip_cnt[i] -= 15;
            }
            if (zip_cnt[i] >= 10) {
                buns[i].letter_cnt += zip_cnt[i];
                ++buns[i].bun_cnt;
                total_letters += zip_cnt[i];
                ++total_buns;
                zip_cnt[i] = 0;
            }
        }
    }

    //按序输出
    printf("ZIP         LETTERS     BUNDLES\n");
    puts("");
    for (int i = 10000; i <= 99999; ++i) {
        if (buns[i].letter_cnt != 0) {
            printf("%d%12d%12d\n", i, buns[i].letter_cnt, buns[i].bun_cnt);
        }
    }
    puts("");

    //清空三位数的桶
    for (int i = 100; i <= 999; ++i) {
        buns[i].letter_cnt = buns[i].bun_cnt = 0;
    }
}

void process2(void) {

    //同3位10份以上打包
    for (int i = 100; i <= 999; ++i) {
        int temp[100][2];
        int cnt = 0, letter_cnt = 0;
        for (int j = 0; j <= 99; ++j) {
            int num = i * 100 + j;
            if (zip_cnt[num] > 0) {
                temp[cnt][0] = num;
                temp[cnt][1] = zip_cnt[num];
                letter_cnt += zip_cnt[num];
                zip_cnt[num] = 0;
                ++cnt;
            }
        }
        while (letter_cnt >= 15) {
            ++buns[i].bun_cnt;
            ++total_buns;
            buns[i].letter_cnt += 15;
            total_letters += 15;
            letter_cnt -= 15;
        }
        if (letter_cnt >= 10) {
            ++buns[i].bun_cnt;
            ++total_buns;
            buns[i].letter_cnt += letter_cnt;
            total_letters += letter_cnt;
            letter_cnt = 0;
        }
        while (letter_cnt > 0) {
            if (temp[cnt - 1][1] >= letter_cnt) {
                zip_cnt[temp[cnt - 1][0]] += letter_cnt;
                break;
            } else {
                zip_cnt[temp[cnt - 1][0]] += temp[cnt - 1][1];
                letter_cnt -= temp[cnt - 1][1];
                --cnt;
            }
        }
        if (buns[i].letter_cnt > 0) {
            printf("%dxx%12d%12d\n", i, buns[i].letter_cnt, buns[i].bun_cnt);
        }
    }
    puts("");
}

void process3(void) {
    //first class 输出
    for (int i = 10000; i <= 99999; ++i) {
        if (zip_cnt[i] > 0){
            printf("%d%12d%12d\n", i, zip_cnt[i], 0);
            total_letters += zip_cnt[i];
        }
    }
    puts("");
}

void output_invalid(void) {
    //非法zip-code输出
    printf("INVALID ZIP CODES\n\n");
    for (int i = 0; i < invalid_cnt; ++i) {
        bool flag = true;
        for (int j = 0; j < i; ++j) {
            if (strcmp(invalid_record[i], invalid_record[j]) == 0) {
                flag = false;
            }
        }
        if (flag) {
            printf("%s\n", invalid_record[i]);
        }
    }

}
int main(void) {
     invalid_cnt = 0;
    while (scanf("%s", buffer) != EOF) {
        if (validity_check(buffer)) {

            //桶排序
            int num = 0;
            for (int i = 0; i < 5; ++i) {
                num = num * 10 + buffer[i] - '0';
            }
            ++zip_cnt[num];
        } else {
            strcpy(invalid_record[invalid_cnt], buffer);
            ++invalid_cnt;
        }
    }

    process1();
    process2();
    process3();
    printf("TOTALS%11d%12d\n\n", total_letters, total_buns);
    output_invalid();
    
    return 0;
}