CF1783C题解

AllenKING_RED · 2023-01-10 14:25:07 · 题解

题目大意

你和其他 n 个选手将参加一项竞赛，每两名选手间会进行一场比赛，此时与你无关的比赛已经比完，从第 1 到第 n 名选手的胜场数分别为从 0 到 n-1 的 n 个整数，你需要同这 n 名选手进行比赛。

对于第 i 名选手，你需要至少 a_i 分钟来准备与其的比赛才能击败他，你的总准备时间为 m 分钟。

现在请你求出按照胜场数排名后你的最高名次，注意这时如果我们没有选择击败一名对手那么他的胜场数会加 1。

如果 3 名选手各 5 胜，1 名选手各 3 胜，2 名选手各 1 胜，那么前 3 名选手将获得第 1 名，第 4 名选手获得第 4 名，最后 2 名选手获得第 5 名。

基本思路

• part 1

  假设我们比赛后胜场数为 x，相当于在 n 个选手中有 n-x 个选手的胜场数会加 1。

  因为这 n 名选手开始时的胜场数分别为 0 到 n-1 的整数，所以在其他选手最后一轮的胜场计算前我们与胜场数为 x 的选手并列。

  由于胜场数最多加 1，所以胜场计入后我们的排名不可能落后于胜场数 x-1 或超过胜场数 x+1 的选手，所以我们的排名只与胜场数为 x 的选手有关，如果战胜他则与其并列否则就落后他一名。

  此时显而易见的可以看出：如果战胜该对手后仍然能保证胜场数为 x 则排名为 n-x 否则为 n-x+1。

  现在我们可以枚举胜场数 x 进行计算，但这样的时间复杂度是 n^2 的不符合要求，需要优化。

• part 2

  我们可以得出一个关键的结论：胜场数最多时的最高排名不会低于其他情况下的最高排名。

  最坏情况下，假设最多胜场数为 a 此时排名为 n-a+1，而另一种情况下胜场数为 a-k，排名为 n-a+k，因为 a 为最多胜场数，所以 k \geq 1，所以 n-a+1 \geq n-a+k，上述结论可以仍然成立，所以我们可以直接考虑胜场数最大时的情况。

• part 3

  根据上述结论，此时我们可以考虑先根据 a_i 排序贪心求出最大胜场数，并标记此时消耗时间最少情况下剩余时间以及选择击败的对手。

  然后我们可以找到计入最后一轮前胜场数与我们相同的选手，此时如果我们已经选择过他，那么肯定可以战胜他，否则我们考虑将之前战胜过的对手进行替换。

  贪心的考虑，我们将之前消耗时间最多的对手与该对手消耗的时间进行对比，如果差值小于剩余的时间，那么我们可以替换，就可以战胜该对手，否则不可以。

  以上即为题解的基本思路。

代码实现

以下为赛时代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
struct mem{
    int id;
    int sum;
}pr[N];
bool cmp(mem x,mem y)
{
    return x.sum<y.sum;
}
int a[N],vis[N];
int n,m;
int T;
signed main(void)
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            pr[i].id=i;
            pr[i].sum=a[i];
            vis[i]=0;
        }
        sort(pr+1,pr+n+1,cmp);
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            if(m>=pr[i].sum)
            {
                ans++;
                m-=pr[i].sum;
                vis[pr[i].id]=1;
            }
        }
        int last=ans;
        int sum=n-ans+1;
        if((vis[ans+1]||m>=(a[ans+1]-pr[last].sum))&&sum>1)--sum;
        cout<<sum<<endl;
    }
    return 0;
}