Sprawiedliwy podział 题解

算法思路

核心思想

这是一个公平分配问题，目标是找到一种物品分配方案，使得双方都不会嫉妒对方。代码采用了一种贪心排序 + 动态分配 + 最终调整的策略。

嫉妒条件理解

• Bajtyna 不会嫉妒：她获得物品的总价值 ≥ Bitek 获得物品对她价值的总和 - 其中最小价值
• Bitek 不会嫉妒：他获得物品的总价值 ≥ Bajtyna 获得物品对他价值的总和 - 其中最小价值

算法详解

1. 数据预处理与排序

vll ord(n);
for (ll i = 0; i < n; i++) {
    ord[i] = i;
}

auto compare = [&](ll f, ll s) {
    return a[f] > a[s];  // 按对Bajtyna的价值降序排序
};
sort(ord.begin(), ord.end(), compare);

关键点：通过索引排序，保持原始数据顺序，按对 Bajtyna 的价值从高到低处理物品。

2. 贪心分配阶段

ll s1 = 0, s2 = 0, mn1 = inf, mn2 = inf;
ll dumb1 = 0, dumb2 = 0;
vll v(n);

for (ll rep = 0; rep < n; rep++) {
    ll i = ord[rep];

    if (s1 <= sum - s1 - a[i]) {
        v[i] = 1;           // 分配给集合1
        s1 += a[i];         // 更新集合1对Bajtyna的价值和
        dumb1 += b[i];      // 更新集合1对Bitek的价值和
        mn1 = min(mn1, a[i]); // 更新集合1中对Bajtyna的最小价值
    } else {
        v[i] = 0;           // 分配给集合0
        s2 += a[i];         // 更新集合2对Bajtyna的价值和
        dumb2 += b[i];      // 更新集合2对Bitek的价值和
        mn2 = min(mn2, a[i]); // 更新集合2中对Bajtyna的最小价值
    }
}

分配逻辑：

• 遍历按价值降序排序的物品
• 将物品分配给当前对 Bajtyna 总价值较小的集合
• 维护两个集合的各种统计信息

3. 最终调整阶段

if (dumb1 < dumb2) {
    for (ll i = 0; i < n; i++) {
        v[i] ^= 1;  // 交换两个集合的分配
    }
}

调整目的：确保最终分配中，获得对 Bitek 总价值较高的集合被标记为 Bitek 的集合。

算法正确性分析

贪心策略的合理性

1. 平衡分配：始终选择当前总价值较小的集合，自然达到平衡
2. 处理顺序：从高价值物品开始处理，避免小价值物品影响大决策
3. 最终调整：通过交换集合来优化对 Bitek 的价值分配

为什么这样能避免嫉妒

虽然代码没有显式验证嫉妒条件，但策略基于：

• 平衡两个集合对 Bajtyna 的价值
• 考虑对 Bitek 的价值进行最终优化
• 题目保证解存在，使得启发式方法有效

复杂度分析

• 排序：$O(n \log n)$
• 贪心分配：$O(n)$
• 最终调整：$O(n)$
• 总复杂度：$O(n \log n)$，对于 $n \leq 5 \times 10^5$ 完全可行

变量含义说明

• s1, s2：两个集合对 Bajtyna 的价值总和
• dumb1, dumb2：两个集合对 Bitek 的价值总和
• mn1, mn2：两个集合中对 Bajtyna 的最小价值
• v[i]：分配方案，1表示集合1，0表示集合0

算法标签

• 贪心算法 (Greedy Algorithm)
• 排序 (Sorting)
• 公平分配 (Fair Division)
• 启发式算法 (Heuristic Algorithm)
• 组合优化 (Combinatorial Optimization)

特殊技巧

1. 索引排序：保持原始顺序，便于最终输出
2. 动态平衡：实时调整分配策略
3. 统计维护：同时跟踪多个价值指标
4. 最终优化：通过简单交换提升方案质量

与之前解法的对比

这个解法与之前看到的解法主要区别在于：

• 更简洁：没有显式的验证步骤，依赖题目保证
• 最终调整：增加了基于 Bitek 价值的交换操作
• 变量命名：使用了更具描述性的变量名

总结

该算法通过巧妙的贪心策略和最终调整，高效地解决了公平分配问题。其核心优势在于：

1. 简单有效：算法逻辑清晰，实现简洁
2. 平衡导向：动态保持两个集合的价值平衡
3. 综合考虑：同时处理对双方的价值分配

体现了贪心算法在实际问题中的实用价值，通过合理的启发式规则在多项式时间内找到优质解。