poj 1010 STAMPS
STAMPS
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 21288 | Accepted: 6352 |
Description
Have you done any Philately lately?
You have been hired by the Ruritanian Postal Service (RPS) to design their new postage software. The software allocates stamps to customers based on customer needs and the denominations that are currently in stock.
Ruritania is filled with people who correspond with stamp collectors. As a service to these people, the RPS asks that all stamp allocations have the maximum number of different types of stamps in it. In fact, the RPS has been known to issue several stamps of the same denomination in order to please customers (these count as different types, even though they are the same denomination). The maximum number of different types of stamps issued at any time is twenty-five.
To save money, the RPS would like to issue as few duplicate stamps as possible (given the constraint that they want to issue as many different types). Further, the RPS won't sell more than four stamps at a time.
Input
The input for your program will be pairs of positive integer sequences, consisting of two lines, alternating until end-of-file. The first sequence are the available values of stamps, while the second sequence is a series of customer requests. For example:
1 2 3 0 ; three different stamp types
7 4 0 ; two customers
1 1 0 ; a new set of stamps (two of the same type)
6 2 3 0 ; three customers
Note: the comments in this example are *not* part of the data file; data files contain only integers.
Output
For each customer, you should print the "best" combination that is exactly equal to the customer's needs, with a maximum of four stamps. If no such combination exists, print "none".
The "best" combination is defined as the maximum number of different stamp types. In case of a tie, the combination with the fewest total stamps is best. If still tied, the set with the highest single-value stamp is best. If there is still a tie, print "tie".
For the sample input file, the output should be:
7 (3): 1 1 2 3
4 (2): 1 3
6 ---- none
2 (2): 1 1
3 (2): tie
That is, you should print the customer request, the number of types sold and the actual stamps. In case of no legal allocation, the line should look like it does in the example, with four hyphens after a space. In the case of a tie, still print the number of types but do not print the allocation (again, as in the example).Don't print extra blank at the end of each line.
Sample Input
1 2 3 0 ; three different stamp types
7 4 0 ; two customers
1 1 0 ; a new set of stamps (two of the same type)
6 2 3 0 ; three customers
Sample Output
7 (3): 1 1 2 3
4 (2): 1 3
6 ---- none
2 (2): 1 1
3 (2): tie
邮票
描述
你最近集邮了吗?
你已经被RPS雇佣来设计他们的新邮资软件。该软件根据客户的需求和当前库存的面值向客户分配邮票。
卢里塔尼亚到处都是与集邮者通信的人。作为对这些人的服务，RPS要求所有的邮票分配有最大数量的不同类型的邮票。事实上，RPS为了取悦顾客，发行了多枚相同面额的邮票(虽然面额相同，但不同的邮票种类不同)。任何时间发行的不同类型邮票最多为25枚。
为了节省资金，RPS希望发行尽可能少的重复邮票(考虑到他们希望发行尽可能多的不同类型的邮票的限制)。此外，RPS一次只能卖出四张以上的邮票。
输入
程序的输入将是一对正整数序列，由两行组成，直到文件结束。第一个序列是邮票的可用价值，而第二个序列是客户的一系列要求。例如:
1 2 3 0 ; three different stamp types
7 4 0 ; two customers
1 1 0 ; a new set of stamps (two of the same type)
6 2 3 0 ; three customers
注意:这个例子中的注释不是数据文件的一部分;数据文件只包含整数。
输出
为每一位顾客印制“最佳”组合邮票(最多四枚)，以配合他们的需要。如果不存在这样的组合，则打印“none”。
“最佳”组合的定义是不同邮票类型的最多数目。如有领带，最好是总数最少的邮票组合。如果仍然平局，最好是单值邮票最高的一套。如果还有领带，就打印“领带”。
对于示例输入文件，输出应该是:
7 (3): 1 1 2 3
4 (2): 1 3
6 ---- none
2 (2): 1 1
3 (2): tie
也就是说，您应该打印客户请求、售出的类型数量和实际邮票。在没有合法分配的情况下，这一行应该与示例中一样，在空格后面有四个连字符。在平局的情况下，仍然打印类型的数量，但不打印分配(同样，如示例所示)。不要在每行的末尾打印额外的空白。
Sample Input
1 2 3 0 ; three different stamp types
7 4 0 ; two customers
1 1 0 ; a new set of stamps (two of the same type)
6 2 3 0 ; three customers
Sample Output
7 (3): 1 1 2 3
4 (2): 1 3
6 ---- none
2 (2): 1 13 (2): tie
问题分析:
深度遍历(dfs)所有可能的组合，选择出最优组合。
组合选择条件:
1.邮票种类多的组合优先选择；
2.在邮票种类一样多的情况下，邮票张数少的组合优先选择；
3.前两个条件一样的情况下，组合中面值最大的邮票进行比较，面值更大的邮票
对应的组合优先选择；
组合条件选择一个判断就够了，难点在于如何遍历得到所有可能的组合，然后再
从这些组合中选择最优解。
代码：
#include
#include
using namespace std;
const int num = 4;
const int stamps = 300; //邮票种类数
bool tie, none;//由题意不言而喻
int total;//当前组合的邮票张数
int types;//每组测试（第一行）的邮票种类数
int end_comb_num;//每位顾客最终输出的组合的邮票张数
int customer;//每位顾客所需的面值
int now[num];//存储当前符合条件的组合
int end_comb[num];//存储最终结果组合
int stamp[stamps];//存储每种邮票的面值
int get_type(int a[], int n) { //获取组合的种类
if (n == 0) return 0;
int type = 1;
sort(a, a+n);
for (int i = 0; i < n-1; i++) {
if (a[i] != a[i+1])
type++;
}
return type;
}
int get_max(int a[], int n) { //获取组合中最大的那个数的值
int max = 0;
for (int i = 0; i < n; i++) {
if (max < stamp[a[i]])
max = stamp[a[i]];
}
return max;
}
void compare() { //比较两个组合，选取最优组合存储
int now_types = get_type(now, total);
int end_comb_types = get_type(end_comb, end_comb_num);
int now_max = get_max(now, total);
int end_comb_max = get_max(end_comb, end_comb_num);
if (end_comb_num == 0 || (now_types > end_comb_types) || (now_types == end_comb_types && total < end_comb_num) ||
(now_types == end_comb_types && total == end_comb_num && now_max > end_comb_max)) { //判断条件
tie = false;
end_comb_num = total;
for (int i = 0; i < total; i++)
end_comb[i] = now[i];
}
if (now_types == end_comb_types && total == end_comb_num && now_max == end_comb_max) {
tie = true;
}
}
void dfs(int n, int value) { //遍历所有合法组合
if (value > customer) return ;
if (value == customer) {
none = true;
compare();
}
if (total == 4) return ;
for (int i = n; i < types; i++) {
now[total] = i;
total++;
dfs(i, value+stamp[i]);
total--;
}
}
void print() { //输出函数
cout << customer << ' ';
if (none == false) {
cout << "---- none" << endl;
}
else {
cout << '(' << get_type(end_comb, end_comb_num) << "): ";
if (tie == true)
cout << "tie" << endl;
else {
sort(end_comb, end_comb+end_comb_num);
for (int i = 0; i < end_comb_num; i++)
cout << stamp[end_comb[i]] << ' ';
cout << endl;
}
}
}
int main() {
int n;
while (cin >> n) {
types = 0;
while (n != 0) {
stamp[types++] = n;
cin >> n;
}
sort(stamp, stamp+types);
cin >> customer;
while (customer != 0) {
total = 0;
end_comb_num = 0;
none = false;
tie = true;
dfs(0, 0);
if (none == true) {
sort(end_comb, end_comb+end_comb_num);
}
print();
cin >> customer;
}
}
return 0;
}
