UVa 10053 Envelopes-开发者社区

题目大意

你有MMM张贺卡（1≤M≤51 \leq M \leq 51≤M≤5）和NNN种信封（M≤N≤10M \leq N \leq 10M≤N≤10）可以选择。每张贺卡需要放入一个独立的信封中，贺卡可以任意角度旋转（包括斜着放），只要它能完全装入信封内即可。每种信封有特定的尺寸（长LiL_iLi，宽WiW_iWi）和价格CiC_iCi。你需要为每张贺卡分配一个信封（不能重复使用同一种信封的同一实体），使得总花费最小。如果无法为所有贺卡分配信封，则输出cannot buy；否则输出最小花费对应的信封编号（按输入顺序从111开始编号）。如果有多组解，输出任意一组即可。

题目分析

这道题看似简单，但实际上涉及几何判断和组合优化两个难点：

几何判断：判断一张尺寸为l×wl \times wl×w的贺卡能否放入一个尺寸为L×WL \times WL×W的信封中。贺卡可以任意旋转（包括斜放），因此不能简单地比较长宽。
组合优化：在NNN种信封中为MMM张贺卡分配信封，每种信封只能使用一次，要求总花费最小。由于M≤5M \leq 5M≤5且N≤10N \leq 10N≤10，数据规模很小，可以直接使用回溯搜索。

几何判断部分

对于贺卡尺寸a=max⁡(l,w)a = \max(l,w)a=max(l,w)，b=min⁡(l,w)b = \min(l,w)b=min(l,w)和信封尺寸A=max⁡(L,W)A = \max(L,W)A=max(L,W)，B=min⁡(L,W)B = \min(L,W)B=min(L,W)，贺卡可以放入信封的条件是：存在一个旋转角度θ\thetaθ，使得贺卡在水平和垂直方向上的投影长度同时不超过信封的对应边长。

用公式表示就是：存在θ∈[0,π/2]\theta \in [0, \pi/2]θ∈[0,π/2]使得
acos⁡θ+bsin⁡θ≤A a \cos\theta + b \sin\theta \leq Aacosθ+bsinθ≤A
asin⁡θ+bcos⁡θ≤B a \sin\theta + b \cos\theta \leq Basinθ+bcosθ≤B
同时成立。

特殊情况：

当a≤Aa \leq Aa≤A且b≤Bb \leq Bb≤B时，可以直接对齐放置（θ=0\theta = 0θ=0或π/2\pi/2π/2）。
当b>Bb > Bb>B时，无论怎么旋转，短边投影至少为bbb，因此不可能放入。
当b≤Bb \leq Bb≤B但a>Aa > Aa>A时，需要通过斜放来减小长边方向的投影。

在代码实现中，我们采用数值方法：在[0,π/2][0, \pi/2][0,π/2]区间内以较小步长（如0.0010.0010.001弧度）搜索θ\thetaθ，检查是否存在满足条件的角度。

组合优化部分

由于MMM很小（最多555），我们可以使用回溯法（DFS\texttt{DFS}DFS）枚举所有可能的分配方案。状态表示为当前已分配的贺卡数量idx和当前总花费currentCost。使用一个布尔数组used记录每种信封是否已被使用。

剪枝优化：当currentCost已经大于等于当前找到的最小花费minCost时，直接返回，不再继续搜索。

复杂度分析：最坏情况下需要检查P(N,M)=N!(N−M)!P(N, M) = \frac{N!}{(N-M)!}P(N,M)=(N−M)!N!种分配方案，当N=10N=10N=10，M=5M=5M=5时，这个值约为302403024030240，加上几何判断的开销，完全在可接受范围内。

解题步骤

读入数据：注意输入可能包含多个测试用例，以0 0结束。
预处理：对每张贺卡和每种信封，判断贺卡能否放入信封（考虑斜放）。
回溯搜索：
- 从第000张贺卡开始，尝试为它分配一个未被使用且能放入的信封。
- 标记该信封为已使用，更新花费，递归处理下一张贺卡。
- 回溯时恢复信封的未使用状态。
- 当所有贺卡都分配完毕时，更新最小花费和最优分配方案。
输出结果：
- 按照题目格式输出测试用例编号。
- 如果找到可行方案，输出每个贺卡对应的信封编号（输入顺序从111开始）。
- 否则输出cannot buy。
- 注意相邻测试用例之间输出一个空行。

代码实现

// Envelopes// UVa ID: 10053// Verdict: Accepted// Submission Date: 2025-12-25// UVa Run Time: 0.000s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structCard{intl,w;};structEnvelope{intL,W,cost,id;};intm,n,minCost;vector<Card>cards;vector<Envelope>envelopes;vector<int>bestAssign,currentAssign;vector<bool>used;boolfound;constdoublePI=acos(-1.0);constdoubleEPS=1e-8;// 判断贺卡能否放入信封（考虑斜放）boolcanFit(constCard&card,constEnvelope&env){doublea=max(card.l,card.w);doubleb=min(card.l,card.w);doubleA=max(env.L,env.W);doubleB=min(env.L,env.W);// 检查是否可以直接对齐放（不旋转或旋转90度）if(a<=A+EPS&&b<=B+EPS)returntrue;if(a<=B+EPS&&b<=A+EPS)returntrue;// 旋转90度// 如果短边b > B，且长边a > A，不可能放（因为旋转只会让投影更大）if(b>B+EPS)returnfalse;// 现在 b <= B，但 a > A，需要斜着放// 数值搜索 θ 在 [0, π/2] 之间for(doubletheta=0.0;theta<=PI/2.0;theta+=0.001){doubleproj1=a*cos(theta)+b*sin(theta);doubleproj2=a*sin(theta)+b*cos(theta);if(proj1<=A+EPS&&proj2<=B+EPS)returntrue;if(proj1<=B+EPS&&proj2<=A+EPS)returntrue;// 信封可旋转}returnfalse;}// 回溯搜索voidbacktrack(intidx,intcurrentCost){if(currentCost>=minCost)return;// 剪枝if(idx==m){minCost=currentCost;bestAssign=currentAssign;found=true;return;}for(inti=0;i<n;++i){if(!used[i]&&canFit(cards[idx],envelopes[i])){used[i]=true;currentAssign[idx]=i;backtrack(idx+1,currentCost+envelopes[i].cost);used[i]=false;}}}intmain(){intcaseNum=1;while(cin>>m>>n&&(m||n)){cards.resize(m);for(inti=0;i<m;++i)cin>>cards[i].l>>cards[i].w;envelopes.resize(n);for(inti=0;i<n;++i){cin>>envelopes[i].L>>envelopes[i].W>>envelopes[i].cost;envelopes[i].id=i+1;}found=false;minCost=INT_MAX;currentAssign.resize(m);bestAssign.resize(m);used.assign(n,false);backtrack(0,0);if(caseNum>1)cout<<endl;cout<<"Case #"<<caseNum++<<endl;if(found){for(inti=0;i<m;++i)cout<<envelopes[bestAssign[i]].id<<endl;}else{cout<<"cannot buy"<<endl;}}return0;}