CF1760F Quests

题意

有 \(n\) 个任务，你每一天都可以选择其中的一个任务完成或不选。当你完成了第 \(i\) 个任务，你将获得 \(a_i\) 元。但是如果你今天完成了一个任务，那么你之后 \(k\) 天内都不能再完成这个任务。

给出两个数 \(c\)，\(d\)，要求求出满足在 \(d\) 天内可以收集至少 \(c\) 元的最大的 \(k\)。

如果不存在这样的\(k\)或者\(k\)可以无限大，输出Impossible或Infinity。

思路

很明显的二分，二分\(k\)即可

每次都尽量安排获得钱多的任务，以\(k\)为一周期，多余的再从大到小安排

这道题我用了前缀和优化，但是似乎不用也可以

注意，在check时要注意如果当前的枚举到的\(k>n\)，那么也只能操作到第\(n\)个任务，而没有更多

而如果将前\(min(d,n)\)大的任务做完一次后，钱已经比\(c\)多，那么就是\(k\)就是无限大

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn=2e5+10;
int n,c,d,ans;
int a[Maxn],f[Maxn];
bool check(int x)
{
    int now=f[min(x+1,n)]*(d/(x+1));
    now+=f[min(n,d-((d/(x+1))*(x+1)))];
    return now>=c;
}
void run()
{
    cin>>n>>c>>d;ans=-1;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1,greater<int>());
    for(int i=1;i<=n;i++) f[i]=f[i-1]+a[i];
    if(f[min(n,d)]>=c)
    {
        cout<<"Infinity"<<endl;
        return;
    }
    int l,r,mid;
    l=0,r=d;
    while(l<=r)
    {
        mid=(l+r)>>1;
        // cout<<l<<" "<<r<<" "<<mid<<endl;
        if(check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    if(ans!=-1) cout<<ans<<endl;
    else cout<<"Impossible"<<endl;
}
signed main()
{
    int t;
    cin>>t;
    while(t--) run();
}