Moe's CF Life

喵哈喽~ 主人，欢迎回来喵！今天我们遇到了一个有趣的传送问题，需要用最少的钱钱去最多的地方玩，听起来就像是计划一次最划算的旅行呢，嘻嘻~ 让本猫娘来帮你分析一下吧，喵~

题目大意

我们现在站在一条长长的数轴上，位置是 0。在 1, 2, ..., n 这些点上，都藏着一个神奇的传送门哦！

我们能做的事情有：

移动：花 1 个金币，向左或者向右走一个单位。
传送：在任何一个点 i，我们可以花 a_i 个金币，使用那里的传送门，然后“咻”的一下回到起点 0！但是，每个传送门只能用一次哦，用完就消失啦，喵。

我们一开始在点 0，口袋里有 c 个金币。我们的目标是，用这些金币，尽可能多地使用传送门！

所以，问题就是，我们最多能使用多少个传送门呢？

题解方法

要解决这个问题，我们得像一只精打细算的小猫咪一样思考，喵！我们想要用最多的传送门，那肯定要先挑那些最“便宜”的用啦，对不对？

那么... 使用一个传送门的“总花费”是多少呢？

假设我们要用在点 i 的传送门。我们从起点 0 出发，要先走到点 i 吧？这段路程需要向右走 i 步，所以路费就是 i 个金币。到了点 i 之后，我们还要支付传送门的费用 a_i。所以，使用点 i 传送门的总成本就是 路费 + 传送门费用 = i + a_i 啦！

既然我们知道了每个传送门的总花费，事情就简单多啦！我们的策略就是：贪心！

首先，我们把所有传送门的总花费都计算出来。对于在点 i 的传送门，它的总花费是 i + a_i。
然后，我们把这些总花费从小到大排个队，就像小猫排队领小鱼干一样，最便宜的排在最前面！
最后，我们从最便宜的那个开始，一个一个地“购买”传送门。只要我们的钱还够，就一直买下去。直到我们的钱不够买下一个最便宜的传送门为止。

这样，我们就能保证在固定的预算内，买到数量最多的传送门啦！因为每次都选最省钱的，肯定能买更多个嘛，喵~

题解

好啦，现在我们来看看代码是怎么实现这个聪明的想法的，喵~

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int n;
    long long c;
    cin >> n >> c; // n 个传送门，c 个金币

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i]; // 读入每个传送门的费用 a_i
    }

    // --- 关键步骤来啦 ---

    // 1. 计算每个传送门的总花费
    // 注意哦，代码里的 a[i] 是第 i+1 个传送门的费用
    // 所以它在点 i+1 上，路费是 i+1
    // 总花费就是 a[i] + (i + 1)
    vector<long long> cost;
    for (int i = 0; i < n; i++) {
        cost.push_back(a[i] + i + 1);
    }

    // 2. 将所有花费从小到大排序
    sort(cost.begin(), cost.end());

    // 3. 贪心购买
    long long total_cost = 0; // 已经花掉的总金币
    int teleporters_used = 0; // 已经使用的传送门数量
    for (int i = 0; i < n; i++) {
        // 如果还能买得起当前最便宜的这个
        if (total_cost + cost[i] <= c) {
            total_cost += cost[i]; // 就买下它！钱钱减少
            teleporters_used++;    // 使用的传送门数量+1
        } else {
            // 哎呀，钱不够了，买不起了，只能停下来了喵
            break;
        }
    }

    cout << teleporters_used << '\n'; // 输出最终结果
}

int main() {
    // 关掉同步可以跑得更快哦，像猫咪一样敏捷！
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t; // 有 t 组测试数据喵
    while (t--) {
        solve();
    }

    return 0;
}

看，代码的逻辑和我们想的一模一样！先算成本，再排序，最后贪心地从最便宜的开始买，直到买不起为止。这样就能得到正确答案啦，喵~

知识点介绍

主人，这次解题我们用到了一个非常重要的思想哦，让本猫娘来给你科普一下吧！

贪心算法 (Greedy Algorithm)
- 贪心算法就像一只看到小鱼干就马上扑过去的小猫，总是做出当前看起来最好的选择，喵~
- 它在每一步都选择一个局部最优解，希望最终能导向全局最优解。在这个问题里，“局部最优”就是选择当前所有未使用的传送门中，总花费最低的那个。
- 为什么这样是对的呢？可以这样想：如果我们选择了一个比较贵的传送门，而放弃了一个更便宜的。那我们完全可以把那个贵的换成便宜的，这样我们花的钱更少了，还能用同样数量的传送门，甚至可能因为省下了钱而能多用一个！所以，先选便宜的总是最划算的，喵！
排序 (Sorting)
- 为了实现贪心，我们得知道哪个是“最便宜”的，对吧？所以我们需要排序！
- 排序是计算机科学里最基本也最重要的操作之一。它能帮我们把一堆乱糟糟的数据变得井井有条，方便我们进行下一步的操作。在这里，我们用 std::sort 把所有传送门的总花费排了个序，这样我们就能轻松地从最小的开始取了。
时间复杂度 (Time Complexity)
- 我们的程序跑得快不快呢？
- 计算所有传送门的花费，需要 O(n) 的时间。
- 给 n 个花费排序，最经典的时间是 O(n log n)。
- 最后遍历一遍去买传送门，又是 O(n) 的时间。
- 所以总的时间主要花在排序上，就是 O(n log n)。对于 n 最大是 20万的情况，这个速度是绰绰有余的，完全不会超时，主人可以放心啦，喵~

好啦，这次的解说就到这里啦！主人明白了吗？只要跟着本猫娘的思路，再难的问题也能迎刃而解的，喵~ 如果还有不懂的，随时可以再来问我哦！

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

题目大意

题解方法

题解

知识点介绍