Bridging the Gap2

题目大意

共有$n(1 \le n \le 5 \times 10^5)$个人处在河的一侧，现在有一艘船，船上只能容纳$k$个人，$k \in [l, r]$。问能否将所有人送至河的另一侧。

解题思路

假设这$n$个人一开始处在河的左侧，可以推出，从左侧划船至右侧在整个过程中是一定可行的。

因为，每次从右侧划回来都至少会带回$l$个人，那么左侧人数一定始终大于$l$，并且他们的体力也一定大于等于$1$，要将所有人送至右侧，自然不会让划回左侧后没体力的人回来，所以从右侧回来的人体力一定大于等于$1$，原本留在左侧的人体力也一定大于等于$1$。

所以，我们只需要保证整个过程中，每次都至少有$l$个人能从右侧划回左侧，并且他们的体力大于等于$2$。

那么首先，我们算出整个过程中从右侧返回左侧的总次数，$S = \lceil\frac{n - r}{r- l}\rceil$，即第一次划向右侧会使左侧减少$r$个人，接下来每个来回都会使左侧减少$r - l$ 个人，最后上取整即可。

接下来算出每个人最多能从右侧返回左侧多少次，$a_i = min(\lfloor\frac{h_i - 1}{2}\rfloor, S)$，即第一次划向右侧后，剩下的体力值能划几个来回，由于将所有人都送至对岸的次数为$S$次，所以还要与$S$取$min$。

将所有人送至河的另一侧等价于每次都至少有$l$个人能从右侧划回左侧，即$Sl$，最后只需要与$\sum a_i$做个比较即可。

因为$a_i \le S$，所以每次划回来第$i$个人只算了一次贡献，如果第$i$个人体力耗尽，那就再找一个人假设为$j$，来继续带他完成这$S$次划船。

所以当$\sum a_i \le Sl$，则可以将所有人送至河的另一侧，反之则不能。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
#define maxn 500100
#define int long long
using namespace std;
const double eps = 1e-8;
int a[maxn];

void solve() {
    int n, l, r, sum = 0, cnt = 0;
    cin >> n >> l >> r;
    sum = (n - r + r - l - 1) / (r - l);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        cnt += min((a[i] - 1) / 2, sum);
    }
    if(cnt >= sum * l)  cout << "Yes\n";
    else  cout << "No\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}