Problem B. 扫雷 1

T0xel 喜欢玩扫雷，但是他玩的扫雷游戏有名为 “地雷探测器” 的特殊道具。

具体来说，T0xel 会进行 n 轮扫雷。每轮扫雷开始之前，T0xel 会获得 1 枚扫雷币。扫雷币在每轮扫雷结束后不会回收，可以保留至下一轮扫雷。T0xel 知道，在第 i 轮（1 ≤ i ≤ n）扫雷中，花费 c_i 枚扫雷币可以购买一个地雷探测器，清除地图中的一个雷。地雷探测器在一轮扫雷中可以购买任意次。

现在 T0xel 想知道，在这 n 轮扫雷中最多能购买多少个地雷探测器呢？

输入格式

第一行，一个正整数 n（1 ≤ n ≤ 2 × 10⁵），表示扫雷轮数。

第二行，n 个正整数 c₁,c₂,...,c_n（1 ≤ c_i ≤ 10⁹）。

输出格式

一行，一个非负整数，表示答案。

样例

提示

对于第一个样例，T0xel 可以选择在第 2 轮与第 6 轮扫雷中各购买一个地雷探测器。具体过程如下：

•     获得 1 枚扫雷币，目前有 1 枚扫雷币。第 1 轮扫雷开始，不购买地雷探测器。

•     获得 1 枚扫雷币，目前有 2 枚扫雷币。第 2 轮扫雷开始，购买一个地雷探测器，目前有 0 枚扫雷币。

•     获得 1 枚扫雷币，目前有 1 枚扫雷币。第 3 轮扫雷开始，不购买地雷探测器。

•     获得 1 枚扫雷币，目前有 2 枚扫雷币。第 4 轮扫雷开始，不购买地雷探测器。

•     获得 1 枚扫雷币，目前有 3 枚扫雷币。第 5 轮扫雷开始，不购买地雷探测器。

•     获得 1 枚扫雷币，目前有 4 枚扫雷币。第 6 轮扫雷开始，购买一个地雷探测器，目前有 1 枚扫雷币。

对于第二个样例，T0xel 可以选择在第 5 轮扫雷中购买两个地雷探测器。

对于第三个样例，T0xel 无法在这 5 轮扫雷中购买地雷探测器。

题解

这题的官方题解思路是贪心，如下：

比赛时脑子抽了，用dp背包写了半天。

赛后跟其他队伍讨论，发现他们用更简单的方法实现了，思路如下：

通过观察，可以发现当执行这样的策略时能得到最优解（至少购买数是一样的）：将每个探测器和出现时的index（也就是假设前面都不买，到这一步时拥有的扫雷币的数量）记录下来并按照价格从小到大的顺序排列，然后从价格最低的开始，优先用当前所拥有的钱数（记录的index - 前面购买花掉的钱cost）够买尽可能多的该探测器，并将cost加上本次的消费，以此类推……

其实比赛时也这样考虑过，但是担心组合的情况会有更优解，就没敢写🥲不知道这个思路有没有破绽？还是说巧合？构造过比较特殊的数据（比如8 5 2 5 5 5 5 5 3，正确输出应该是3）也是没问题的。如果发现有漏洞，欢迎在下面的评论区讨论~

这个思路实现很简单，下面的代码已经在CF的gym中一发AC。

代码实现

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long

struct Node {
    int price;
    int i;
};

int cost = 0;
vector<Node> a;

bool cmp(const Node& a, const Node& b)
{
    return a.price < b.price;
}

int main()
{
    int n;
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].price;
        a[i].i = i + 1;
    }

    sort(a.begin(), a.end(), cmp);

    int cnt = 0;
    for (Node i : a) {
        int money = i.i - cost;
        int num = money / i.price;
        if (money >= i.price) {
            cnt += num;
            cost += num * i.price;
        }
    }
    cout << cnt;

    return 0;
}