企业官网建设流程全解析

题目描述

Ruritanian\texttt{Ruritanian}Ruritanian邮政服务（RPS\texttt{RPS}RPS）需要设计一种软件，根据顾客需求和现有邮票面值，为顾客分配邮票。每次分配最多使用444张邮票，且要求总面值恰好等于顾客需求。在满足此条件的组合中，优先选择不同面值类型最多的组合；若类型数相同，则选择总邮票张数最少的组合；若仍相同，则选择单张面值最高的组合（即组合中最大面值最大）；若仍然无法区分，则输出tie。若不存在任何组合，则输出none。

输入格式

输入包含多组数据。每组数据由两行整数序列组成，交替出现，直到文件结束。第一行为可用邮票的面值序列，以正整数给出，以0结束。第二行为顾客需求序列，以正整数给出，以0结束。序列中的每个整数均用空格分隔，可能跨行。

输出格式

对于每个顾客需求，输出一行：

• 若存在合法组合，输出需求值、括号内的类型数、冒号，然后按非递减顺序列出所选邮票面值（若唯一），若存在多个并列最优则输出tie。
• 若无合法组合，输出需求值后跟---- none。

具体格式见样例。

样例

输入

1 2 3 0 7 4 0 1 1 0 2 3 0

输出

7 (3): 1 1 2 3 4 (2): 1 3 2 (2): 1 1 3 (2): tie

题目分析

本题本质上是带约束的组合搜索问题。邮票数量nnn不超过252525（因为最多不同面值类型数为252525），且每次最多使用444张邮票，因此可以使用深度优先搜索（DFS\texttt{DFS}DFS）枚举所有可能的组合（可重复选取，但相同面值的邮票视为不同个体，但由于只关心面值和类型数，等价于允许重复使用同一种面值）。对每个组合计算其面值总和、使用的张数、不同面值类型数以及最大面值，按照题目定义的优先级比较，记录最优组合。

由于nnn较小，枚举所有组合的数量级为O(n4)O(n^4)O(n4)，完全可接受。

解题思路

1. 读取邮票面值序列存入数组stamps[0..n-1]，n为邮票个数（包括重复面值）。
2. 对于每个顾客需求request，使用DFS\texttt{DFS}DFS搜索所有可能的组合：
   • 参数：当前深度depth（已选邮票数），起始索引idx（允许选择从idx开始的邮票，且允许重复选同一张，因此递归时idx不变），当前面值和sum。
   • 剪枝：若depth > 4或sum > request则返回。
   • 若sum == request，则得到一个合法组合，计算类型数（通过set<int>存储不同面值）、总张数（depth+1）、最高面值，并与当前最优比较，若更优则更新最优组合。
3. 比较规则：
   • 先比较类型数，更大者优。
   • 若类型数相同，比较总张数，更小者优。
   • 若总张数相同，比较最高面值，更大者优。
   • 若三者均相同，则视为并列最优，保留多个组合（用best向量存储所有并列最优组合）。
4. 若best为空，输出none；若best大小为111，输出唯一组合；否则输出tie。

注意输出时组合中的面值按非递减顺序输出。

复杂度分析

• 搜索深度最大444，每次选择有nnn种可能，最坏枚举n4n^4n4个组合，n≤25n \le 25n≤25，约390625390625390625，完全可行。
• 空间复杂度O(4)O(4)O(4)，用于存储当前组合。

代码实现

// Stamps// UVa ID: 648// Verdict: Accepted// Submission Date: 2018-12-28// UVa Run Time: 0.020s//// 版权所有（C）2018，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;vector<vector<int>>best;inttypes,total,highest,n,request;intstamps[32],used[4];voiddfs(intdepth,intidx,intsum){if(depth>4||sum>request)return;if(sum==request){boolbetter=false;set<int>diff;for(inti=0;i<depth;i++)diff.insert(used[i]);if(diff.size()>types){best.clear();better=true;}elseif(diff.size()==types){if(depth+1<total){best.clear();better=true;}elseif(depth+1==total){inth=0;for(inti=0;i<depth;i++)h=max(h,stamps[used[i]]);if(h>highest){best.clear();better=true;}elseif(h==highest){better=true;}}}if(better){types=diff.size();total=depth+1;highest=0;vector<int>vs;for(inti=0;i<depth;i++){highest=max(highest,stamps[used[i]]);vs.push_back(stamps[used[i]]);}sort(vs.begin(),vs.end());best.push_back(vs);}return;}for(inti=idx;i<n;i++){used[depth]=i;dfs(depth+1,i,sum+stamps[i]);}}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intvalue;while(cin>>value){n=0;stamps[n++]=value;while(cin>>value,value>0)stamps[n++]=value;while(cin>>request,request>0){best.clear();types=0,total=10,highest=0;dfs(0,0,0);cout<<request;if(best.size()==0)cout<<" ---- none\n";else{cout<<" ("<<types<<"):";if(best.size()==1){for(inti=0;i<best[0].size();i++)cout<<' '<<best[0][i];cout<<'\n';}elsecout<<" tie\n";}}}return0;}

总结

本题通过深度优先搜索枚举所有不超过444张邮票的组合，并按照多级优先级比较选出最优。关键点在于正确实现组合的生成和比较逻辑，注意处理并列最优时输出tie。由于数据规模小，暴力搜索完全可行。该解法体现了递归搜索和状态比较的基本技巧，适合作为组合枚举的练习。