问题分析

有 $N$ 个等级，等级 $i$ 有 $x_i$ 个停车位和 $y_i$ 个订阅用户。需要将用户分配到停车位，使得 $U - D$ 最大化，其中：

• $U$：分配到的停车位等级 $t$ 小于订阅等级 $s$ 的用户数（点赞）
• $D$：分配到的停车位等级 $t$ 大于订阅等级 $s$ 的用户数（差评）

关键观察

1. 问题转化

对于订阅等级为 $s$ 的用户：

• 分配到等级 $t < s$ 的停车位：获得 $+1$ 分
• 分配到等级 $t = s$ 的停车位：获得 $0$ 分
• 分配到等级 $t > s$ 的停车位：获得 $-1$ 分

2. 贪心策略

假设我们已经确定了某个分配方案。考虑调整：

• 如果一个用户从等级 $t_1$ 换到 $t_2$，且 $t_1 < t_2$，那么：
  • 如果该用户的订阅等级 $s$ 满足 $t_1 < s \le t_2$：分数从 $+1$ 变成 $-1$，减少 $2$ 分
  • 如果 $s \le t_1$：分数不变（都是 $+1$）
  • 如果 $s > t_2$：分数不变（都是 $-1$）

因此，将用户分配到更低等级的停车位通常更优。

算法思路

核心思想

从高等级到低等级处理，维护：

• sum：当前待分配的用户总数（比当前等级高的用户）
• v：当前可以避免产生差评的最小用户数
• ans：累计的点赞数

算法流程

int ans = 0, sum = 0, v = 0;
for (int i = n - 1; i >= 0; i--) {
    // 步骤1：用当前等级的停车位服务等待的用户（产生点赞）
    int d = min(a[i], sum);
    sum -= d, a[i] -= d;
    ans += d;
    
    // 步骤2：更新可以避免差评的用户数
    v = min(v, sum) + min(a[i], b[i]);
    
    // 步骤3：加入当前等级的用户
    sum += b[i];
}
printf("%d\n", ans - (sum - v));

变量解释

• a[i]：等级 $i$ 的停车位数 $x_i$
• b[i]：订阅等级 $i$ 的用户数 $y_i$
• sum：比当前等级高的用户总数
• v：可以分配到合适停车位避免差评的用户数
• ans：点赞总数

算法详解

为什么从高到低处理？

从高等级（差停车位）向低等级（好停车位）处理，可以：

1. 优先用好的停车位服务高等级用户（产生点赞）
2. 尽量让低等级用户分配到不低于他们订阅等级的停车位

每一步的含义

1. int d = min(a[i], sum);

   • 用当前等级 $i$ 的停车位服务等待的高等级用户
   • 每个这样的分配产生一个点赞

2. v = min(v, sum) + min(a[i], b[i]);

   • min(v, sum)：之前可以避免差评的用户数不能超过当前等待用户数
   • min(a[i], b[i])：当前等级的用户可以分配到当前等级的停车位（不产生差评）

3. sum += b[i];

   • 加入当前等级的用户，他们成为等待分配的用户

4. 最终答案：ans - (sum - v)

   • ans：点赞总数
   • sum - v：必然会产生差评的用户数（无法避免）
   • 最终分数 = 点赞数 - 差评数

正确性证明

定理：最优解中，点赞数最大化为：

1. 从高到低处理每个等级
2. 对于每个等级 $i$，用它的停车位尽可能服务高等级用户
3. 剩余停车位用于服务同等级用户（避免差评）

证明思路：

1. 点赞最大化：如果有一个停车位等级 $i$ 和一个用户等级 $j > i$，分配它们会产生点赞。由于停车位总数有限，应该优先给更高等级的用户（更大的 $j-i$ 差值和）。

2. 差评最小化：对于订阅等级 $i$ 的用户：

   • 如果分配到等级 $< i$：点赞
   • 如果分配到等级 $= i$：无影响
   • 如果分配到等级 $> i$：差评

   因此，应尽量让他们分配到等级 $\ge i$ 的停车位。

3. 贪心选择：从高到低处理，每次尽可能用当前停车位服务高等级用户，剩余停车位留给同等级用户。

复杂度分析

• 时间复杂度：$O(N)$，单次遍历
• 空间复杂度：$O(N)$，存储输入数组
• 可以处理 $N \le 3 \times 10^5$ 的大数据

示例分析

样例1

输入：
2
3 3  (停车位)
1 3  (用户)

处理过程：
i=1: a[1]=3, b[1]=3
  d = min(3, 0) = 0
  ans = 0
  v = min(0, 0) + min(3, 3) = 0 + 3 = 3
  sum = 0 + 3 = 3
  
i=0: a[0]=3, b[0]=1  
  d = min(3, 3) = 3
  sum = 3 - 3 = 0
  a[0] = 3 - 3 = 0
  ans = 0 + 3 = 3
  v = min(3, 0) + min(0, 1) = 0 + 0 = 0
  sum = 0 + 1 = 1

输出：ans - (sum - v) = 3 - (1 - 0) = 2

样例4

输入：
4
2 1 1 8  (停车位)
0 4 4 0  (用户)

处理过程（简化）：
最终计算得 ans=3, sum=8, v=5
输出：3 - (8 - 5) = 0 - 3 = -1

总结

本题的关键在于：

1. 将问题转化为分数最大化问题
2. 发现贪心性质：从高到低处理，优先用好的停车位服务高等级用户
3. 维护两个关键变量：点赞数 ans 和可避免差评的用户数 v