The Curse of the Frog - Codeforces Solution • MuXinCG's Blog

青蛙掌握了 $n$ 种魔法跳跃，每种跳跃有最大距离限制，但每隔一定次数会触发回退诅咒。本文分析如何以最少的回退次数到达目标点。

题目描述#

在一条无限数轴上，一只青蛙坐在点 $0$ 处。经过多年的修炼，它掌握了 $n$ 种独特的魔法跳跃。第 $i$ 种跳跃允许它向前跳跃不超过 $a_i$ 个单位。换句话说，如果它在整数点 $k$ ，跳跃后可以落在 $k$ 到 $k + a_i$ 之间的任意整数点上。

但魔法总有代价——它被诅咒了。在第 $i$ 种跳跃的每第 $b_i$ 次尝试之前（即第 $b_i, 2b_i, 3b_i, \ldots$ 次使用第 $i$ 种跳跃之前），青蛙会回退 $c_i$ 个单位！也就是说，如果它在点 $k$ ，它会先到达点 $k - c_i$ ，然后跳跃后可以落在 $k - c_i$ 到 $k - c_i + a_i$ 之间的任意整数点上。

青蛙的目标是到达点 $x$ ，同时使回退次数最少。请帮助青蛙——找到它到达目标所需的最少回退次数，或判断它无法到达点 $x$ 。

思路分析#

首先我们观察题目，发现当青蛙选择跳跃种类的时候，只要选择 $b_i - 1$ 次，那么就不会触发回退，那么我们就可以直接使用免费步数进行尝试，如果免费步数已经跳跃到了终点，那么我们就不用触发回退，如果免费步数没有到达终点，我们就需要后续计算

免费步数没有到达终点，那么我们必须触发一次回退，由于本题是找触发回退最少的情况而不是步数最少的情况，因此我们不考虑步数，仅考虑回退次数，我们考虑每一个步数种类在一次回退中最多能前进多少步，因此计算公式为 $total = a_i * b_i - c_i$ ，找到最大的total，进行讨论

如果total小于零，证明最高的total下，进行一次循环会倒退，并且我们花费了所有的免费步数还没有到达终点，也就是说，我们不能到达终点，因此输出-1

如果total不小于零，那么就可以根据total计算出回退次数，由于选出的total是所有步数中距离/回退次数最大的，因此算出的回退次数肯定是最小的，容易证明这是最优解

代码实现#

// Problem: 1075DIV2
// URL: https://codeforces.com/contest/1075/problem/DIV2
// Tags: B
//    ███╗   ███╗██╗   ██╗██╗  ██╗██╗███╗   ██╗ ██████╗ ██████╗ 
//    ████╗ ████║██║   ██║╚██╗██╔╝██║████╗  ██║██╔════╝██╔════╝ 
//    ██╔████╔██║██║   ██║ ╚███╔╝ ██║██╔██╗ ██║██║     ██║  ███╗
//    ██║╚██╔╝██║██║   ██║ ██╔██╗ ██║██║╚██╗██║██║     ██║   ██║
//    ██║ ╚═╝ ██║╚██████╔╝██╔╝ ██╗██║██║ ╚████║╚██████╗╚██████╔╝
//    ╚═╝     ╚═╝ ╚═════╝ ╚═╝  ╚═╝╚═╝╚═╝  ╚═══╝ ╚═════╝ ╚═════╝ 
//                                                              

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

const int MAXN = 1e5 + 10;
int n;
long long x;
struct step{
    int a;
    int b;
    int c;
    long long total;
} steps[MAXN];

void solve() {
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> steps[i].a >> steps[i].b >> steps[i].c;
        steps[i].total = (long long)steps[i].a * steps[i].b - steps[i].c;
        x -= (long long)(steps[i].b - 1) * steps[i].a;
    }
    if (x <= 0) {
        cout << 0 << '\n';
        return;
    }
    long long best = 0;
    for (int i = 1; i <= n; i++)
        best = max(best, (long long)steps[i].total);
    if (best <= 0) {
        cout << -1 << '\n';
        return;
    }
    cout << (x + best - 1) / best << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

cpp

复杂度分析#

输入 $n$ 个步数的a,b,c三个元素，为 $O(n)$

计算出每一个步数的 $total$ ，为 $O(n)$

使用免费步数 $O(n)$

找出最高total $O(n)$

最终计算 $O(1)$

综上所述，复杂度为 $O(n)$

The Curse of the Frog - Codeforces Solution

题目描述#

思路分析#

代码实现#

复杂度分析#

Related Posts