代码分析

核心思路

这是一个反悔贪心算法，通过逆向处理和优先队列来最小化总代价。

算法步骤

1. 排序处理

sort(a, a + n);

将所有人按照 $A_i$（要求的朋友数）从小到大排序。

2. 逆向扫描 + 堆维护

for (int i = n - 1; i >= 0; i--) {
    pq.push(-a[i].S);  // 小根堆技巧：存入负值
    while (num < a[i].F - i) {
        num++;
        ans -= pq.top();  // 取出最小代价
        pq.pop();
    }
}

关键理解

变量含义

• num：当前需要付费的人数
• ans：总代价
• pq：存储可能需要付费的人的代价（用小根堆实现）

核心条件：a[i].F - i

• i 是当前处理的人在排序后的索引
• a[i].F 是第 i 个人要求的朋友数
• a[i].F - i 表示：在位置 i 处，还需要额外付费的人数

工作原理

1. 从后往前处理：

   • 从要求最高的朋友开始处理
   • 这样确保高要求的人更容易被满足

2. 堆的作用：

   • 存储所有候选人的代价
   • 当需要付费时，选择代价最小的人付费

3. 小根堆技巧：

   pq.push(-a[i].S);  // 存入负值
   ans -= pq.top();   // 取出时再取负，得到最小值
   

样例演示

以样例1为例：

输入：
4
3 3
1 2  
0 5
3 4

排序后：
(0,5), (1,2), (3,3), (3,4)

逆向处理：
i=3: 加入代价4，要求3-3=0，不付费
i=2: 加入代价3，要求3-2=1，付费最小代价3
i=1: 加入代价2，要求1-1=0，不付费  
i=0: 加入代价5，要求0-0=0，不付费

总代价：3

时间复杂度

• 排序：$O(N \log N)$
• 堆操作：$O(N \log N)$
• 总复杂度：$O(N \log N)$

算法正确性

该算法保证：

1. 所有交友条件都被满足
2. 每次付费都选择当前代价最小的人
3. 通过逆向处理确保高要求的人优先被考虑

总结

这是一个经典的反悔贪心应用，通过排序+优先队列高效解决了最小化代价问题，适用于大规模数据。