Drwale——题解

问题分析

我们有两个伐木工要处理一堆木材，木材按顺序堆叠。每次伐木工完成当前任务后，就从堆顶取下一块木材。如果两人同时完成，Bajtek 优先取木材。

关键点：

• 木材的顺序会影响完成时间
• 我们要找到最坏的排列，使得完成时间最长
• 这实际上是一个对抗性调度问题

核心思路

经过分析，我们可以发现最优策略是：

1. 将最耗时的木材放在最后
2. 将前 n-1 块木材尽可能平均地分配给两个伐木工
3. 用最后的大木材来平衡时间差

数学建模

设：

• 前 n-1 块木材总时间：$S = \sum_{i=1}^{n-1} a_i$
• 分配给 Bajtek 的时间：$X$
• 分配给 Bitek 的时间：$S - X$
• 最大木材时间：$M = a_n$

完成时间的计算：

• 如果 $X \geq S - X$：Bajtek 先取大木材，完成时间 = $\max(X + M, S - X)$
• 如果 $S - X > X$：Bitek 先取大木材，完成时间 = $\max(X, S - X + M)$

统一公式：

$$\text{ans} = \frac{S + 2M - |2X - S|}{2}$$

约束条件：$|2X - S| \leq M$（时间差不能超过最大木材时间）

算法设计

问题转化为：找到满足条件的 X，使得完成时间最大

步骤：

1. 排序木材，最大放最后
2. 用背包问题判断前 n-1 块木材能组成哪些总时间 X
3. 对所有满足 $|2X - S| \leq M$ 的 X 计算完成时间，取最大值

优化技巧：

• bitset 优化：用位运算加速背包 DP
• 二进制优化：高效处理重复的木材时间

代码详解

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 5e6 + 1e3 + 7;  // 总时间上限 + 缓冲

int n, a[N];
bitset<N> f;  // f[i] 表示能否组成总时间 i

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // 读入数据
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    // 关键步骤1：排序，最大木材放最后
    sort(a + 1, a + n + 1);
    
    // 初始化：总时间0是可达的
    f[0] = 1;
    
    // 统计前n-1块木材中每种时间的出现次数
    unordered_map<int, int> cnt;
    for (int i = 1; i < n; i++)
        cnt[a[i]]++;
    
    int sum = 0;  // 前n-1块木材的总时间
    
    // 关键步骤2：多重背包的二进制优化
    for (auto [x, y] : cnt) {
        sum += x * y;  // 累加总时间
        
        int u = y;  // 剩余数量
        int v = 1;  // 当前拆分大小
        
        // 二进制拆分：将y拆成1,2,4,...的幂次组合
        while (u) {
            int t = min(u, v);  // 这次拆分的数量
            
            // bitset优化：f << (t*x) 表示所有可达时间加上t*x
            f |= f << (t * x);
            
            u -= t;
            v <<= 1;  // 二进制增长
        }
    }
    
    int M = a[n];  // 最大木材时间
    int ans = 0;
    
    // 关键步骤3：寻找最优解
    for (int i = 0; i < N; i++) {
        if (!f.test(i))  // 如果时间i不可达，跳过
            continue;
        
        int A = i;      // Bajtek的总时间
        int B = sum - i; // Bitek的总时间
        
        // 检查时间差是否满足条件
        if (abs(A - B) > M)
            continue;
        
        // 计算完成时间并更新答案
        int finish_time = (sum + M + M - abs(A - B)) / 2;
        ans = max(ans, finish_time);
    }
    
    cout << ans << "\n";
    return 0;
}

关键部分详细解释

1. 二进制优化原理

while (u) {
    int t = min(u, v);
    f |= f << (t * x);
    u -= t;
    v <<= 1;
}

作用：将 y 个相同物品（时间 x）拆分成 1,2,4,... 的组合，这样可以用 $O(\log y)$ 次操作完成 $O(y)$ 的工作。

例子：如果有 13 个时间 x 的木材，拆分成：

• 1个：处理 1×x
• 2个：处理 2×x
• 4个：处理 4×x
• 6个：处理 6×x（因为 13-1-2-4=6）

2. Bitset 优化原理

f |= f << (t * x);

• f << k：将所有可达时间右移 k（即加上 k）
• f |= ...：合并新的可达状态
• 每次操作是 $O(N/w)$，其中 w 是机器字长（通常64）

3. 完成时间计算公式

(sum + M + M - abs(A - B)) / 2

推导：

• 总工作量：$S + M$
• 如果时间差为 $d = |A-B|$，那么大木材可以填补这个差距
• 最优情况下，完成时间 = $\frac{S + M + (M - d)}{2} = \frac{S + 2M - d}{2}$

复杂度分析

• 时间复杂度：$O(\frac{nS}{w})$，其中 w=64
• 空间复杂度：$O(S)$

对于 $S \leq 5\times 10^6$，这个复杂度是可接受的。

测试样例验证

样例1：n=3, [2,3,1]

• 排序后：[1,2,3]，M=3
• 前2块总时间 S=1+2=3
• 可能的分配：A=0,B=3 或 A=1,B=2 或 A=2,B=1 或 A=3,B=0
• 满足 |2X-3|≤3 的有：X=0,1,2,3
• 最大完成时间：X=1 时，(3+6-1)/2=4 ✓

样例2：n=6, a_i=i

• 排序后：[1,2,3,4,5,6]，M=6
• S=1+2+3+4+5=15
• 最大完成时间：13 ✓

学习要点

1. 问题转化：将复杂调度问题转化为背包问题
2. bitset优化：处理大规模布尔状态的高效方法
3. 二进制优化：多重背包的标准优化技巧
4. 数学分析：通过推导得出简洁的最优解公式