题解：2024牛客暑期多校第3场——A [Bridging the Gap 2]

英文题干

A group of n walkers arrives at a riverbank at night. They want to cross the river using a boat which is initially on their side. The boat can hold at most R walkers at a time and requires at least $L(1 ≤ L < R)$ walkers to operate.

Rowing the boat is a tiring task. Each time the boat is used to transport a group of walkers to the other side of the river, all walkers on the boat must have stamina greater than 0, and each walker's stamina decreases by 1 after the trip. Initially, the i-th walker $(1 ≤ i ≤ n )$ has a stamina value of $h_i$ .

You need to determine if it is possible to transport all the walkers to the other side of the river using the boat.

Input:

The first line of input contains three integers $n,L,R(1 \leq L<R<n \leq 5 × 10^5)$ ，denoting the number of walkers，the minimum and the maximum number of walkers to use the boat at a time, respectively.

The second line of input contains $n$ integers $h_1, h_2,... , h_n (1 ≤ h_i ≤ 5 × 10^5)$ ， where $h_i (1 ≤ i ≤ n)$ denotes the stamina value of the i-th walker.

Output:

If it is possible to transport all the walkers to the other side of the river using the boat, output "Yes" in the first line (without quotes). Otherwise, output "No" in the first line (without quotes). You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will all be considered as positive replies.

中文题干

一群步行者在晚上到达河岸。他们想用最初在他们这边的船过河。该船一次最多可容纳 R 个步行者，并且需要至少 $L(1 ≤ L < R)$ 个步行者操作。

划船是一项累人的任务。每次用船将一群步行者运送到河的另一边时，船上的所有步行者都必须具有大于0的耐力，并且每个步行者的耐力在旅行后减少 1。最初，第 i 个步行者 $(1 ≤ i ≤ n )$ 的耐力值为 $h_i$ 。

您需要确定是否可以使用船将所有步行者运送到河的另一边。

思路

又是一道思维题）

直接模拟显然是不行的（至少是O( $n^2$ )会TLE），所以尝试从整体的数学模型角度考虑问题。

首先，每个人渡河所消耗的体力值是一样的，因此我们不必关注每个人具体每一次的过河情况，只需要统计能提供的总有效过河人次和所需的总过河人次进行比较。
用一个数组存每个人的有效运输次数（可以回来接人的轮数），可将其视为每个人能提供的人头数。然后计算把所有人全运过去的完整所需轮数并换算为人头数（人头数=轮数*L）。
最后，将每个人能提供的人次（取该名步行者能提供的有效运输次数和总所需轮次的最小值）进行加和。若能提供的总人次超过所需人次，则证明能完全过河。

（期间注意一些特殊的情况可以直接结束程序，详见代码）

AC代码

时间复杂度：O( $n$ )

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int infmin = 0xc0c0c0c0;
const int infmax = 0x3f3f3f3f;
const int maxn = 5e5 + 10;

int h[maxn];
ll tranRound[maxn]; // 每个人的有效运输次数

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, L, R;
    cin >> n >> L >> R;

    int reuseableCnt = 0;  // 耐力值大于2的步行者数量
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        if (h[i] > 2) {
            reuseableCnt++;
            tranRound[i] = (h[i] - 1) / 2;
        }
    }

    // 一遍过
    if (n <= R) {
        cout << "Yes";
        return 0;
    }

    // 不能一遍过的情况下，没有足够的人回来继续接人
    if (reuseableCnt < L) {
        cout << "No";
        return 0;
    }

    ll wholeTrans = (n - R - 1) / (R - L) + 1;  // 需要的完整运输次数 (-1是为了上取整)
    ll wholeNum = wholeTrans * L;  // 需要的总操作人数

    for (int i = 1; i <= n; i++) {
        if (h[i] > 2) {
            wholeNum -= min(tranRound[i], wholeTrans);
        }
    }

    if (wholeNum <= 0)
        cout << "Yes";
    else
        cout << "No";

    return 0;
}
// Inspired by 你的代码有点耗时