Codeforces Round 835 (Div. 4) — F. Quests

Codeforces Round 835 (Div. 4) — F. Quests

训练思维的算法题，值得一做，题目直接展示了，后面会有题解，不要有畏难心理，纯手搓思路！

F. Quests

time limit per test 3 seconds

memory limit per test 256 megabytes

There are n quests. If you complete the i-th quest, you will gain ai coins. You can only complete at most one quest per day. However, once you complete a quest, you cannot do the same quest again for k days. (For example, if k=2 and you do quest 1 on day 1, then you cannot do it on day 2 or 3, but you can do it again on day 4.)

You are given two integers c and d. Find the maximum value of k such that you can gain at least c coins over d days. If no such k exists, output Impossible. If k can be arbitrarily large, output Infinity.

Input

The input consists of multiple test cases. The first line contains an integer t (1≤t≤10^4) — the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers n,c,d (2≤n≤2⋅10^5; 1≤c≤10^16; 1≤d≤2⋅10^5) — the number of quests, the number of coins you need, and the number of days.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤10^9) — the rewards for the quests.

The sum of n over all test cases does not exceed 2⋅10^5, and the sum of d over all test cases does not exceed 2⋅10^5.

Output

For each test case, output one of the following.

If no such k exists, output Impossible.

If k can be arbitrarily large, output Infinity.

Otherwise, output a single integer — the maximum value of k such that you can gain at least c coins over d days.

Please note, the checker is case-sensitive, and you should output strings exactly as they are given.

Example

InputCopy

6
2 5 4
1 2
2 20 10
100 10
3 100 3
7 2 6
4 20 3
4 5 6 7
4 100000000000 2022
8217734 927368 26389746 627896974
2 20 4
5 1

OutputCopy

2
Infinity
Impossible
1
12
0

Note

In the first test case, one way to earn 5 coins over 4 days with k=2 is as follows:

Day 1: do quest 2, and earn 2 coins.

Day 2: do quest 1, and earn 1 coin.

Day 3: do nothing.

Day 4: do quest 2, and earn 2 coins.

In total, we earned 2+1+2=5 coins.

In the second test case, we can make over 20 coins on the first day itself by doing the first quest to earn 100 coins, so the value of k can be arbitrarily large, since we never need to do another quest.

In the third test case, no matter what we do, we can’t earn 100 coins over 3 days.

题解

核心思路：排序 + 贪心判断 + 二分答案。

固定一个冷却时间后，可以贪心求出最多能拿多少金币；由于冷却时间越大，限制越强，能拿到的金币不会增加，因此可以二分最大可行值。

一、题意转化

题目要求找到最大的 k，使得在 d 天内至少获得 c 枚金币。

其中 k 的含义是：如果今天做了某个任务，那么接下来的 k 天都不能再做同一个任务。

例如 k = 2：

所以，同一个任务的重复周期并不是 k，而是：

m = k + 1

代码里更方便二分的是周期 m，最后答案再转回：

k = m – 1

二、固定周期 m 后怎么求最大收益

先把所有任务奖励从大到小排序。

排序后：

a[0] ≥ a[1] ≥ a[2] ≥ …

也就是说：

固定周期 m 后，最优策略就是按奖励从高到低循环做任务。

如果 m = 3，任务下标会这样循环：

0, 1, 2, 0, 1, 2, 0, 1, 2, …

这个循环正好可以用：

int idx = i % m;

表示。

其中 i 表示第几天，从 0 开始。

例如 m = 3：

所以第 i 天尝试做的任务就是：

a[i % m]

三、为什么要判断 idx < n

如果周期 m 比任务数量 n 大，那么有些周期位置没有任务可以做。

例如：

n = 2, m = 4

任务只有：

a[0], a[1]

但是 i % m 会循环出：

0, 1, 2, 3, 0, 1, 2, 3, …

当 idx = 2 或 idx = 3 时，不存在对应任务，所以当天只能休息。

因此判断收益时需要写：

if (idx < n) {
res += a[idx];
}

四、为什么可以二分

周期 m 越大，说明同一个任务要等更久才能重复做。

所以：

因此可行性具有单调性：

如果某个 m 可行，那么更小的 m 一定可行。

如果某个 m 不可行，那么更大的 m 一定不可行。

所以可以用二分查找最大的可行周期 m。

二分模板：

while (l < r) {
int mid = (l + r + 1) >> 1;

if (check(mid)) {
l = mid;
} else {
r = mid – 1;
}
}

这里要找最大可行值，所以使用右中位数：

int mid = (l + r + 1) >> 1;

五、边界解释

1. 为什么 l = 0

周期 m 的最小合法值是 1。

因为：

m = k + 1

而 k 的最小值是 0，所以 m 最小是 1。

这里把 l 初始化为 0：

int l = 0;

0 不是合法周期，而是一个标记。

它表示当前还没有找到任何可行的周期。

如果最后 l == 0，说明连 m = 1 都不可行。

m = 1 对应 k = 0，也就是每天都可以做收益最高的任务。

如果这样都不能达到 c，答案就是：

Impossible

2. 为什么 r = d + 1

总共只有 d 天。

如果：

m > d

那么在这 d 天里，同一个任务不会被重复做。

例如 d = 4, m = 5，前四天的下标是：

0, 1, 2, 3

还没循环回来，天数已经结束。

所以 m = d + 1 可以用来代表“不需要重复任务”的情况。

如果 m = d + 1 仍然可以达到 c，说明根本不用重复任务也能完成目标。

那么 k 可以任意大，答案就是：

Infinity

六、算法流程

七、正确性证明

引理 1：固定周期时，优先选择高奖励任务最优

对于固定的周期 m，每天能做的任务位置是确定循环的。

由于奖励越高越应该尽早完成，并且越早完成也越早进入冷却，之后越早可以再次完成，所以把任务奖励从大到小排序，并按顺序循环选择，不会比其他选择更差。

因此固定周期时，该贪心策略可以得到最大收益。

引理 2：可行性具有单调性

当周期 m 增大时，同一个任务重复所需的间隔变长。

因此高奖励任务出现的频率不会增加，总收益不会增加。

所以：

• 如果某个 m 可行，则更小的 m 一定可行；
• 如果某个 m 不可行，则更大的 m 一定不可行。

因此可以二分最大的可行周期。

引理 3：特殊情况判断正确

如果 l == 0，说明连最小周期 m = 1 都不可行。

m = 1 对应 k = 0，是限制最宽松的情况。

如果这种情况都不能达到目标，则不存在任何合法 k，输出 Impossible 正确。

如果 l == d + 1，说明周期大于总天数时仍然可行。

这表示在 d 天内完全不需要重复任务也能达到目标，因此 k 可以任意大，输出 Infinity 正确。

综上，算法正确。

八、易错点总结

本题最容易错的是变量含义和二分边界。

1. 不要混淆 k 和 m

题目要求输出的是 k，但代码二分的是：

m = k + 1

所以最后输出：

cout << l – 1 << '\\n';

2. 不要把输出判断写进 while 循环

错误结构：

while (l < r) {
...
if (l == d + 1) {
cout << "Infinity\\n";
return;
}
}

正确结构：

while (l < r) {
...
}

if (l == d + 1) {
cout << "Infinity\\n";
} else if (l == 0) {
cout << "Impossible\\n";
} else {
cout << l – 1 << '\\n';
}

3. 二分最大值时要取右中位数

应写成：

int mid = (l + r + 1) >> 1;

如果写成：

int mid = (l + r) >> 1;

当 l 和 r 相邻时，可能死循环。

4. 关于数组写法

ll a[n] 在 Codeforces 的 GNU C++ 中通常可以通过，但不是标准 C++。

更稳的写法是全局数组：

const int N = 200010;
ll a[N];

或者使用 vector：

vector<ll> a(n);

九、完整代码

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

typedef long long ll;

const int N = 200010;
ll a[N];

void solve() {
int n, d;
ll c;

cin >> n >> c >> d;

for (int i = 0; i < n; i++) {
cin >> a[i];
}

sort(a, a + n, greater<ll>());

/*
题目中的 k 是冷却天数。
代码中二分的是周期 m = k + 1。
最后答案需要输出 k = m – 1。
*/

int l = 0, r = d + 1;

while (l < r) {
int mid = (l + r + 1) >> 1;

ll res = 0;

for (int i = 0; i < d; i++) {
int idx = i % mid;

if (idx < n) {
res += a[idx];
}

if (res >= c) {
break;
}
}

if (res >= c) {
l = mid;
} else {
r = mid – 1;
}
}

if (l == d + 1) {
cout << "Infinity\\n";
return;
}

if (l == 0) {
cout << "Impossible\\n";
return;
}

cout << l – 1 << '\\n';
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int t;
cin >> t;

while (t—) {
solve();
}

return 0;
}

十、复杂度分析

排序复杂度为 O(n log n)。

二分周期 m 的次数为 O(log d)。

每次判断最多模拟 d 天，所以判断部分复杂度为 O(d log d)。

因此总时间复杂度为：

O(n log n + d log d)

空间复杂度为：

O(n)

十一、总结

本题关键是理解：

周期 m = k + 1

固定周期后，按奖励从高到低循环选择任务即可得到最大收益。

由于周期越大，限制越强，收益不会增加，因此可以二分最大的可行周期。

最终答案为：

k = m – 1

核心： 排序 + 贪心模拟 + 二分答案。