问题理解

这道题是一个比较复杂的区间安排与动态规划问题。 我们有：

• l 张课桌，每张长度 w
• n 个初始学生，每人已占据一个位置 p_i 在某个课桌 k_i 上
• 每个笔记本电脑长度 d，必须完全放在课桌内，且不能重叠
• 又来 m 个新学生，需要安排所有 n+m 个学生
• 可以移动初始学生（算作一次操作），问最少移动多少初始学生

关键点：

• 笔记本电脑不能重叠 ⇒ 在同一个课桌上，相邻笔记本电脑必须间隔至少 d 的距离
• 可以移动到非整数位置
• 目标是最小化移动的初始学生数

---

核心思路

1. 容量计算

每张课桌能容纳的最大笔记本电脑数为： [ \text{capacity} = \lfloor \frac{w}{d} \rfloor + 1 ] 因为第一个从 0 开始，最后一个结束位置 ≤ w-d。

2. 问题转化

对于每张已经有学生的课桌，我们考虑：

• 如果不移动任何该课桌上的学生，能额外放多少新电脑？
• 如果移动 k 个学生，能释放出多少空间（能放多少电脑）？

这变成一个分组背包问题：

• 每组对应一张课桌
• 每组有若干选择：移动 0,1,2,... 个学生，获得不同的容量增益

3. 单课桌子问题

对于一张有 m 个学生的课桌，给定学生位置 pos[0..m-1]（已排序）：

定义：

• g[j] = 移动 j 个学生后，该课桌能容纳的总电脑数
• 计算方式：尽量紧凑排列，利用空隙

实际上代码中：

• b[k] = 移动 k 个学生后，该课桌能放的总电脑数
• 通过 DP 计算最优排列方式

---

代码详解

1. 数据读入与分组

map<int, vector<int>> v;
for (int i = 1; i <= n; i++) {
    int k, p;
    cin >> k >> p;
    v[k].push_back(p);
}

按课桌分组存储学生位置。

2. 单课桌 DP

对每个课桌：

sort(pos.begin(), pos.end());
vector<int> g(m + 1, -1e18);
g[0] = 0;
vector<int> b(m + 1);

• g[j] 辅助计算
• b[k] 最终结果：移动 k 个学生后的容量

核心计算：

for (int i = 0; i < m; i++) {
    int x = pos[i];
    for (int j = m; j >= 1; j--) {
        int val = (pos[i] + g[j - 1]) / d + 1;
        b[j] = max(b[j], val + (w - pos[i] - d) / d);
        g[j] = max(g[j], val * d - (pos[i] + d));
    }
}
b[0] = w / d;  // 不移动任何学生时的容量

这里在计算：如果移动 j 个学生，能获得的最大容量。

3. 分组背包

vector<int> dp(n + 1);  // dp[x] = 移动 x 个学生能获得的总容量
for (auto [e, pos] : v) {
    // ... 计算 b[k] ...
    vector<int> ndp(n + 1);
    for (int k = 0; k <= m; k++) {
        int rk = m - k;  // 该课桌移动的学生数
        for (int j = 0; j + rk <= n; j++)
            ndp[j + rk] = max(ndp[j + rk], dp[j] + b[k]);
    }
    dp.swap(ndp);
}

这是标准的分组背包：

• 状态：已移动的学生数 → 总容量
• 对每个课桌，枚举移动该课桌的学生数，更新状态

4. 空课桌容量

dp[i] += (l - v.size()) * (w / d);

空课桌每张能放 w/d 个电脑。

5. 查询处理

int e;
cin >> e;
e += n;  // 总学生数
int ans = lower_bound(dp.begin(), dp.end(), e) - dp.begin();
if (ans > n) ans = -1;

找最小的移动学生数，使得总容量 ≥ 总学生数。

---

复杂度分析

• 单课桌处理：O(m²)，总 O(n²)（因为 ∑m = n）
• 分组背包：O(n²)
• 总复杂度：O(n²)，对 n ≤ 3000 可行

---

学习要点

1. 问题转化：将移动学生问题转化为容量最大化问题
2. 分组背包：处理多组物品，每组只能选一个的方案
3. 单课桌最优排列：贪心计算移动 k 个学生后的最大容量
4. 空课桌处理：直接计算额外容量

这个解法结合了组合优化与动态规划，是竞赛中处理复杂安排问题的典型方法。