题解：Paper-, er, Transcript-Folding Game（P3475）

一、题目分析

本题要求计算将成绩单折叠至能放入信封的最少次数。关键规则：

• 每次只能水平或垂直折叠，折叠后对应维度减半
• 成绩单放入信封时不能倾斜，需满足长和宽均不超过信封的长和宽

二、解题思路

1. 维度处理：
   首先将信封和成绩单的长、宽统一为最大值和最小值，方便比较：

   • 信封：$env_max = max(a, b)`, `env_min = min(a, b)$
   • 成绩单：$trans_max = max(c, d)$, $trans_min = min(c, d)$

2. 折叠策略：
   每次优先折叠较长的边（$trans_max$），直到成绩单的长和宽均不超过信封的长和宽。
   若折叠长后仍不满足，再折叠宽，以此类推。

三、代码解析

#include<iostream>
using namespace std;

// 判断成绩单是否超出信封尺寸
bool envelop(double a, double b, double c, double d) {
    if (a >= c && b >= d) return false;  // 能放入
    return true;  // 不能放入
}

int main() {
    double a, b, c, d;
    int cnt;
    double env_max, env_min, trans_max, trans_min;
    
    while (cin >> a >> b >> c >> d) {
        cnt = 0;
        // 计算信封和成绩单的最大、最小维度
        env_max = (a > b) ? a : b;
        env_min = (a < b) ? a : b;
        trans_max = (c > d) ? c : d;
        trans_min = (c < d) ? c : d;
        
        // 循环折叠直到能放入信封
        while (envelop(env_max, env_min, trans_max, trans_min)) {
            // 优先折叠较长的边
            if (env_max < trans_max) {
                cnt++;
                trans_max /= 2;  // 长折叠减半
            }
            if (env_min < trans_min) {
                cnt++;
                trans_min /= 2;  // 宽折叠减半
            }
            // 重新更新长和宽的最大值、最小值
            trans_max = (trans_max > trans_min) ? trans_max : trans_min;
            trans_min = (trans_max < trans_min) ? trans_max : trans_min;
        }
        cout << cnt << endl;
    }
    return 0;
}

四、关键步骤解析

1. 维度标准化
   将信封和成绩单的长、宽转换为最大值和最小值，消除方向影响：

   • 信封：$(env_max, env_min)$，其中$env_max ≥ env_min$
   • 成绩单：$(trans_max, trans_min)$，其中$trans_max ≥ trans_min$

2. 折叠判断函数
   $envelop(a, b, c, d)$判断$c×d$的成绩单能否放入$a×b$的信封：
   [ \text{envelop}(a,b,c,d) = \begin{cases} \text{false}, & \text{若 } a \geq c \text{ 且 } b \geq d \ \text{true}, & \text{否则} \end{cases} ]

3. 折叠过程

   • 若成绩单的长$trans_max$超过信封的长$env_max$，折叠长（$trans_max /= 2$），次数+1
   • 若成绩单的宽$trans_min$超过信封的宽$env_min$，折叠宽（$trans_min /= 2$），次数+1
   • 每次折叠后重新计算$trans_max$和$trans_min$

五、复杂度分析

• 时间复杂度：最坏情况下，成绩单维度为$2^k$，需折叠$k$次，复杂度为O(log(max(c,d)))。
• 空间复杂度：O(1)，仅使用常数级变量。

六、可能的优化

1. 数学推导折叠次数：
   直接计算长和宽需要折叠的次数，取最大值：
   [ \text{fold_max} = \lceil \log_2(\frac{\text{trans_max}}{\text{env_max}}) \rceil ]
   [ \text{fold_min} = \lceil \log_2(\frac{\text{trans_min}}{\text{env_min}}) \rceil ]
   但需处理无法整除的情况（如$trans_max=3$, $env_max=1$需要折叠2次：3→1.5→0.75）。

2. 位运算优化：
   使用位运算计算折叠次数，提高效率，但代码可读性可能下降。