思路

二分答案 + 贪心。

贪心选择： 在任意一段可用天数里，都应当优先做收入最高的工作，因此先把所有工作按收入从高到低排序，并求出前缀和 $f[i]$（前 $i$ 高收入工作的总收入）。

对给定 $k$ 判断可行性： 同一个工作做一次后必须休息 $k$ 天才能再做，所以一种长度 $k+1$ 的循环节里最多做 $\min(k+1,n)$ 份互不相同的工作；由于收入已降序，取前 $\min(k+1,n)$ 个收益最大。

• 完整周期数 $p=\lfloor d/(k+1)\rfloor$，剩余天数 $y=d\bmod(k+1)$；
• $d$ 天内最大收入为 $p\cdot f[\min(k+1,n)] + f[\min(n,y)]$。

若该值 $\ge c$ 则 $k$ 可行，否则不可行。可以验证收入随 $k$ 单调不增（休息日越多，同样天数内能做的高收入工作只会更少），因此可以二分。

两个边界情况：

• Impossible：只做收入最高的那一份工作（最好的单日收益）做满 $d$ 天都不够，即 $f[1]\cdot d<c$；
• Infinity：当 $k\ge d-1$ 时，一个周期就覆盖了全部 $d$ 天，可以每天做一份不同的工作（$d>n$ 时做完 $n$ 份为止），总收入为 $f[\min(d,n)]$。若它 $\ge c$，则任意大的 $k$ 都可行，答案无上界。

二分实现： 在 $[0,10^6)$ 上找第一个不可行的 $k$（check 返回真表示不可行），答案即它减一。取 $r=10^6$ 作为不可行上界：当 $k$ 大到超过 $d$ 后，每个周期仍只能做 $n$ 种工作、周期却被拉长，收入只会下降，数据范围保证答案远小于 $10^6$，用它当右端点安全。

复杂度： 每个测试用例排序 $O(n\log n)$，二分 $O(\log 10^6)$ 次、每次 $O(1)$，合计 $O(n\log n)$；空间 $O(n)$。

代码

#include<bits/stdc++.h>
#define int long long
#define dd double
#define str string
#define el cout << '\n'
#define re return
#define ff first
#define ss second
#define pll pair<int,int>
#define pdd pair<dd,dd>
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;

void go(){
    int n,c,d;cin>>n>>c>>d;          // 工作数、目标金额、可用天数
    vector<int>a(n+1, 0), f(n+1, 0);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        f[i] = f[i-1]+a[i];
    }
    sort(a.begin()+1, a.end() , greater<int>());   // 收入从高到低
    for(int i=1;i<=n;i++){
        f[i] = f[i-1]+a[i];          // 重算前缀和
    }

    if(f[min(d, n)] >= c){
        // 每个工作只做一次就够，k 可以任意大
        cout<<"Infinity";
    }else if(f[1]*d < c){
        // 连收入最高的工作做满 d 天都不够
        cout<<"Impossible";
    }else{

        // 返回 1 表示 k=m 时无法在 d 天内赚到 c，返回 0 表示可以
        auto check = [&](int m)->int{
            int p = d/(m+1), y = d%(m+1);           // 完整周期数、剩余天数
            int res = p*f[min(m+1, n)] + f[min(n, y)];

            if(res < c){
                return 1;                               // 不可行
            }else{
                return 0;                               // 可行
            }
        };

        // 二分第一个不可行的 k，答案是其前一个
        int l = 0, r = 1e6, mid, ans = 0;
        while (l+1<r)
        {
            mid = (l+r)/2;
            int cur = check(mid);

            if(cur){
                r = mid;                 // 不可行，收缩右界
                ans = r;
            }else{
                l = mid;                 // 可行，增大左界
            }

        }

        cout<<max(0ll, ans-1);
    }
    el;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int _=1;
    cin >>_;                         // 多组测试数据
    while(_--){
        go();
    }
    return 0;
}