题目分析

这是 POI 2012 Warehouse Store 的题解代码。题目要求：

• 每天上午进货 $a_i$，下午客人购买 $b_i$
• 存货足够时可以选择是否卖
• 存货不足时无法卖
• 求最多能满足的客人数

代码思路解析

核心算法：贪心 + 反悔机制

for (int i = 1; i <= n; ++i) {
    sum += a[i];
    
    if (sum >= b)
        q.emplace(b, i), sum -= b;  // 直接满足
    else if (!q.empty() && b < q.top().first) {
        sum += q.top().first - b;   // 反悔：退掉之前代价大的
        q.pop();
        q.emplace(b, i);            // 满足当前代价小的
    }
}

算法步骤：

1. 维护当前库存 sum
2. 优先队列存储已满足的客人（按 $b_i$ 从大到小）
3. 直接满足：如果库存足够，直接满足当前客人
4. 反悔替换：如果库存不够，但当前 $b_i$ 小于已满足客人中最大的 $b_i$，就替换掉那个客人

算法正确性证明

这种贪心+反悔的策略保证了：

• 总是保持最多的客人数量
• 用更小的 $b_i$ 替换更大的 $b_i$，为后续客人留出更多库存
• 最终得到的就是最优解

复杂度分析

• 时间复杂度：$O(n \log n)$（每个元素最多入队出队一次）
• 空间复杂度：$O(n)$

样例演示

输入：

6
2 2 1 2 1 0  
1 2 2 3 4 4

执行过程：

• 第1天：库存2，满足客人1（b=1），库存剩1
• 第2天：库存3，满足客人2（b=2），库存剩1
• 第3天：库存2，满足客人3（b=2），库存剩0
• 第4天：库存2，不满足客人4（b=3）
• 第5天：库存3，替换客人3→客人5（4<2? 否）
• 第6天：库存3，替换客人2→客人6（4<2? 否）

最终：客人1,3,5 → 排序后输出1,2,4