扭蛋

题意

扭蛋机中有 $n$ 种扭蛋，第 $i$ 种扭蛋有 $a_i$ 个。

• 消耗 $1$ 枚扭蛋币，可以随机获得 $1$ 个扭蛋；
• 消耗任意 $k$ 个扭蛋，可以兑换 $1$ 个指定币；
• 消耗 $1$ 个指定币，可以获得任意指定种类的 $1$ 个扭蛋。

求至少需要多少枚扭蛋币，才能保证最终拥有每种扭蛋各至少一个。

思路

为了使新种类尽可能晚出现，最坏情况下，数量多的扭蛋会优先被抽到。

因此，先将 $a_i$ 从大到小排序：

枚举已经保证获得 $i$ 种不同扭蛋的时刻。

设前 $i-1$ 种扭蛋的数量之和为 $s$，即：

那么，抽取 $s+1$ 次后，一定已经获得至少 $i$ 种不同的扭蛋。

此时保留已经获得的 $i$ 种扭蛋各一个，需要保留 $i$ 个扭蛋。因此，可用于兑换指定币的扭蛋数量为：

还缺少 $n-i$ 种扭蛋，需要兑换 $n-i$ 个指定币，共需要消耗：

个扭蛋。

若当前可消耗的扭蛋数量不足，则继续抽取补足$(n-i)\times k-(s+1-i)$个扭蛋。

因此，当已经保证获得 $i$ 种扭蛋时，需要的扭蛋币数量为：

枚举所有 $i$，取最小值即可。

复杂度分析

冒泡排序的时间复杂度为 $O(n^2)$。

枚举答案的时间复杂度为 $O(n)$。

因此，每组数据的总时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。

由于所有测试数据的 $n$ 之和不超过 $3000$，所以可以通过。

参考代码

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

void solve()
{
    int n,k;
    cin >> n >> k;
    //vector<int>a(n+1);
    int a[n+1]={0};
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    //sort(a.begin()+1,a.end(),greater<int>());
    for(int i=1;i<=n-1;i++)
    {
        for(int j=1;j<=n-i;j++)
        {
            if(a[j]<a[j+1])swap(a[j],a[j+1]);//swap就是交换两个变量的值的c++函数。
           //swap(a[j],a[j+1])等价于
           //int temp=a[j];
           //a[j]=a[j+1];
           //a[j+1]=temp;
        }
    }

    int ans=1e18;
    int s=0;
    for(int i=1;i<=n;i++)
    {
        int res=s+1+max((n-i)*k-(s+1-i),0ll);
        ans=min(ans,res);
        s+=a[i];
    }

    cout << ans << '\n';
}

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

不用swap版

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

void solve()
{
    int n,k;
    cin >> n >> k;
    //vector<int>a(n+1);
    int a[n+1]={0};
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    //sort(a.begin()+1,a.end(),greater<int>());
    for(int i=1;i<=n-1;i++)
    {
        for(int j=1;j<=n-i;j++)
        {
            if(a[j]<a[j+1])
            {
                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }

        }
    }

    int ans=1e18;
    int s=0;
    for(int i=1;i<=n;i++)
    {
        int res=s+1+max((n-i)*k-(s+1-i),0ll);
        ans=min(ans,res);
        s+=a[i];
    }

    cout << ans << '\n';
}

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