题目理解

我们有一个星系，包含 $N$ 个星球。每个星球 $i$ 有两个属性：

• $A_i$：在该星球可以搜集到的燃料量
• $B_i$：前往该星球需要花费的燃料量

狐狸星小队从星球 $P$ 出发，目标是：

1. 最大化搜集到的总燃料量
2. 在满足目标1的前提下，最大化访问的不同星球数量

问题转化

设当前燃料量为 $F$，访问一个星球需要满足：

• $F \geq B_i$（有足够燃料前往）
• 访问后燃料变化：$F = F - B_i + A_i = F + (A_i - B_i)$

因此，访问一个星球的净收益为 $A_i - B_i$。

算法思路

核心观察

1. 起始点处理：起始星球 $P$ 的燃料可以直接获得，无需花费
2. 可行性条件：只有 $A_i \geq B_i$ 的星球才可能提供净收益
3. 贪心策略：优先访问花费 $B_i$ 小的星球，这样可以尽早积累燃料访问更多星球

算法步骤

1. 初始化：

   • 总燃料 $Ans$ = 起始星球 $P$ 的 $A_P$
   • 访问星球数 $Cnt$ = 1（起始星球）

2. 筛选星球：

   • 排除起始星球（已访问）
   • 只考虑 $A_i \geq B_i$ 的星球（净收益非负）

3. 排序：将候选星球按 $B_i$（花费）从小到大排序

4. 贪心访问：

   • 按顺序尝试访问每个候选星球
   • 如果当前燃料 $Ans \geq B_i$，则访问该星球：
     • $Ans = Ans + (A_i - B_i)$
     • $Cnt = Cnt + 1$
   • 否则停止（后续星球花费更大，更不可能访问）

代码实现分析

#include <bits/stdc++.h>
#define maxn 100005
using namespace std;

int N, M, P, Ans, Cnt = 1;
struct FHY {
    int w, v;  // w = A_i - B_i (净收益), v = B_i (花费)
    bool operator<(const FHY &B)const {
        return v < B.v;  // 按花费从小到大排序
    }
} A[maxn];

int main() {
    cin >> N >> P;
    
    for (int i = 1; i <= N; i++) {
        int a, b;
        cin >> a >> b;
        
        if (i == P)
            Ans += a;  // 起始星球直接获得燃料
        else if (a >= b)  // 只考虑净收益非负的星球
            A[++M] = {a - b, b};  // 记录净收益和花费
    }
    
    sort(A + 1, A + 1 + M);  // 按花费排序
    
    for (int i = 1; i <= M; i++)
        if (Ans >= A[i].v) {  // 有足够燃料前往
            Ans += A[i].w;    // 更新总燃料（净收益）
            Cnt++;           // 增加访问星球数
        } else {
            break;           // 无法访问后续星球
        }
    
    cout << Ans << endl << Cnt << endl;
    return 0;
}

算法正确性证明

1. 最优性：按花费排序可以确保在有限燃料下访问尽可能多的星球
2. 可行性：只考虑 $A_i \geq B_i$ 的星球保证访问不会减少总燃料
3. 终止条件：当无法访问当前星球时，后续星球花费更大，更不可能访问

复杂度分析

• 时间复杂度：$O(N \log N)$，主要来自排序操作
• 空间复杂度：$O(N)$，存储候选星球信息

样例验证

对于样例：

5 2
12 12
10 100
8 3
4 5
25 15

处理过程：

1. 起始星球2：$Ans = 10$, $Cnt = 1$
2. 候选星球：星球3(5,3), 星球1(0,12), 星球5(10,15)
3. 排序后：星球3(5,3), 星球1(0,12), 星球5(10,15)
4. 访问：
   • 星球3：$10 \geq 3$ → $Ans=15$, $Cnt=2$
   • 星球1：$15 \geq 12$ → $Ans=15$, $Cnt=3$
   • 星球5：$15 \geq 15$ → $Ans=25$, $Cnt=4$

输出：25 和 4，与样例一致。

算法标签

• 贪心算法
• 排序
• 模拟

总结

本题的关键在于识别出只有净收益非负的星球才值得访问，并通过贪心策略（按花费排序）来最大化访问星球数量。算法简洁高效，能够处理大规模数据（$N \leq 10^5$）。