题目理解

我们有一个 $N$ 排的考场，每排有 $6$ 个座位（A-F），中间是过道（在 C 和 D 之间）。有 $M$ 个考生要提前离开，他们可以选择去前面的保密室或后面的保密室。

每个离开的考生的不满度计算为 $Ax + By$，其中：

• $x$：去保密室时经过的考生人数
• $y$：进入保密室时保密室内已有的考生数
• $A, B$：给定的常数参数

目标是安排每个考生选择的保密室（前或后），使得所有 $M$ 个考生的总不满度最小。

问题分析

1. 经过的考生数计算

对于一个在座位 $(R_i, C_i)$ 的考生：

• 同排的阻挡：从座位到过道路径上的考生

  • 如果座位在左侧（A,B,C）：需要经过同排中列号小于等于自己且更靠近过道的考生
  • 如果座位在右侧（D,E,F）：需要经过同排中列号大于等于自己且更靠近过道的考生

• 行间的阻挡：从所在行到出口行之间的过道上的考生

  • 如果去前面的保密室：需要经过第 $1$ 行到第 $R_i-1$ 行中过道上的考生
  • 如果去后面的保密室：需要经过第 $R_i+1$ 行到第 $N$ 行中过道上的考生

2. 不满度模型

设第 $i$ 个考生：

• 如果去前面的保密室：经过 $a_i$ 个考生，此时前面保密室已有 $p$ 人
• 如果去后面的保密室：经过 $b_i$ 个考生，此时后面保密室已有 $q$ 人

则不满度为：

• 去前面：$A \cdot a_i + B \cdot p$
• 去后面：$A \cdot b_i + B \cdot q$

算法思路

1. 关键观察

代码中的核心思路是：

1. 预处理阻挡人数：

   • 对于每个考生，计算他去前面和后面保密室时分别会经过多少考生
   • 这些值在考生按顺序离开时是动态变化的（因为前面的考生离开后座位就空了）

2. 排序与贪心：

   • 定义 $g[i] = b_i - a_i$，表示选择后面相比选择前面节省的经过人数
   • 将考生按 $g[i]$ 排序，$g[i]$ 越小（负得越多）的考生越倾向于选择前面

3. 数学优化：

   • 总不满度可以表示为关于选择前面考生数量的二次函数
   • 通过求导或直接枚举找到最优的分配方案

2. 具体实现

代码中的主要步骤：

1. 初始化：

   for (int i = 1; i <= n; ++i) {
       for (int j = 0; j < 6; ++j) v[i][j] = 1;  // 所有座位初始有考生
       s[i] = 2;  // 每排过道处有2个考生（C和D座位）
       add(i, 2); // 树状数组记录每排过道考生数
   }
   

2. 处理每个离开的考生：

   • 更新座位状态：v[x][p] = 0
   • 如果是过道座位（C或D），更新树状数组
   • 计算去前面的经过人数 ax = get(x)（使用树状数组求前缀和）
   • 计算去后面的经过人数 bx = sum - ax + s[x]
   • 记录差值 g[i] = bx - ax

3. 最优分配：

   • 将考生按 g[i] 排序
   • 找到最优的分界点 x，前 x 个考生去前面，后 m-x 个去后面
   • 计算总不满度

代码核心逻辑

// 计算最优分配
std::sort(g, g + m);
int x = 0;
for (; x < m; ++x) {
    if ((vf[x + 1] - vf[x]) * b + g[x] * 1ll * a < 0)
        cnt += g[x];
    else
        break;
}

// 计算总不满度
tmp.set(cnt + ct);
tmp = tmp * xa;        // A * (总经过人数)
ans.set(vf[x]);        
ans = ans * xb;        // B * (保密室人数相关项)
ans = ans + tmp;       // 总不满度

其中：

• cnt：总经过人数的优化值
• ct：特殊座位的额外处理
• vf[x]：与保密室人数相关的二次项

算法标签

• 数据结构：树状数组（用于快速计算前缀和）
• 贪心算法：按节省值排序并选择最优分配
• 数学优化：二次函数最值问题
• 动态规划思想：顺序处理考生，维护当前状态

时间复杂度

• 预处理：$O(M \log N)$（树状数组操作）
• 排序：$O(M \log M)$
• 最优分配：$O(M)$
• 总复杂度：$O(M \log N + M \log M)$，对于 $M \leq 6N \leq 6 \times 10^5$ 是可接受的

总结

这道题的关键在于：

1. 准确计算每个考生去不同保密室的经过人数
2. 发现总不满度可以表示为关于分配方案的二次函数
3. 通过排序和贪心找到最优解
4. 使用树状数组高效维护动态变化的座位状态

代码通过巧妙的数学建模和数据结构应用，高效解决了这个复杂的优化问题。