「DDL分配」题解（基于代码分析）

题意简化

$n$ 个人分 $k$ 个DDL，第 $i$ 个人提出方案，需要超过 $v_i$ 的人同意（按比例？实际是人数），否则被踢掉。

目标：求前 $i$ 个人时，最后一个人能分到多少DDL，否则输出 $-1$。

核心思想：贪心 + 优先队列

1. 投票条件

设当前有 $len$ 个人，第 $i$ 个人需要超过 $v_i$ 的同意票。

假设他需要 $x$ 票同意，则必须满足：

从代码看，实际是 $x > v_i$ 的人数？

代码中：x = max(0ll, x) 和 d = len - x，其中 x 来自输入的 $v_i$ 减1。

2. 关键变量

• len：当前还"活着"的人数
• sum：当前已分配的DDL总数
• lazy：延迟标记，表示已踢掉的人的统一补偿
• X：这次可以复活的人数
• 优先队列 q：存储（分配数 - lazy, 人数）

3. 算法流程

对每个人 $i$：

第一步：检查合法性

如果 $v_i > i$，当前人必死，输出 $-1$。

第二步：踢人计算

计算需要踢掉的人数 d = len - x，其中 x = v_i - 1（需要同意的票数）。

用优先队列踢人：总是踢掉当前分配最少的人（DDL拿得少的人更容易被踢）。

第三步：分配决策

如果踢完人后 len == x（刚好剩下需要的人数）：

• 检查剩余DDL是否足够：sum + len*(lazy+1) <= k
• 如果够：计算当前人能拿到的DDL = k - sum - len*(lazy+1)
• 更新状态：lazy++（给所有已踢掉的人补偿1个DDL）
• 将之前踢掉的人复活（X 个人），加入队列
• 当前人加入队列

如果不够或条件不满足：当前人必死，输出 $-1$。

关键点

1. 贪心策略

• 总是踢掉分配最少的人（最小化损失）
• 给被踢的人统一补偿（lazy）
• 可能的话复活之前踢掉的人

2. 数据结构

• 优先队列维护（分配数，人数）对
• lazy 延迟标记，避免频繁更新

3. 合法性检查

• 如果 $v_i > i$，不可能有足够同意票
• 如果剩余DDL不够，当前人无法分配

样例解释

输入：

5
100
1 1 2 2 3

过程：

1. $v_1=1$：需要0票同意，所有人(1人)活，最后1人拿100
2. $v_2=1$：需要0票，所有人(2人)活，最后1人拿100
3. $v_3=2$：需要1票，踢掉1个拿最少的人，最后1人拿99
4. $v_4=2$：需要1票，情况类似，最后1人拿99
5. $v_5=3$：需要2票，踢掉1人，最后1人拿98

输出：100 100 99 99 98

代码特点

• 使用 pair<int,int> 存储（值，人数），减少队列操作
• lazy 标记优化
• 快速IO（ios::sync_with_stdio(false)）
• 注意 long long（$k \le 10^{18}$）

复杂度

• 每个 $i$：优先队列操作 $O(\log n)$
• 总复杂度：$O(n \log n)$，可过 $n=10^6$