题解 CF1183G 【Candy Box (hard version)】

· · 题解

感觉D题的思路对G题有一定的提示作用。

首先对于每一个种类记录一个cnt_1和cnt_0表示两种糖果的种类。为了方便令cnt=cnt_1+cnt_0

我们考虑D题的思路：将所有的cnt排序，然后从大到小贪心选取。

放到这道题上，为了选出来最优答案，我们还是需要将所有cnt排序后进行一次贪心，但是我们很快发现这样做并不能得到最大的f_i=1的数量。

怎么办呢？容易发现答案可以拆成若干个互不相同的数相加（就是贪心的过程中每一个种类的糖果选取的数量），那么我们可以想到，对于一个数x，能够凑出x这么多糖果的一定是数量大于等于x的糖果种类（这不是废话吗）。

接下来我们的问题就是对每一个x选择一个糖果种类x_i，使得最后\sum\min(x,cnt_1[x_i])最大。

所以对于一个数x，我们把所有cnt\ge x的都丢到一个集合中，然后选取集合中选取cnt_1最大的那个糖果种类加入答案中。

这样做一定是最优的，证明如下：

考虑最优答案，我们发现如果最优答案下x选择的不是cnt_1最大的，那么检查当前cnt_1最大的是否被选择，如果没有被选择，我们一定可以让x改选最大的，答案至少不会变劣。

如果cnt_1最大的已经被选择了，我们考虑选择cnt_1的那个数y与x的大小关系。如果y<x，那么就将x,y选择的进行交换，否则不会违反我们从大到小贪心的规则。

最后我们需要实现一个数据结构，支持插入和查询最大值，用一个堆就可以了。

时间复杂度O(n\log n)。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int t,n,cnt0[200005],cnt1[200005],sa[200005];
priority_queue<int>q;
bool cmp(int a,int b)
{
    return cnt0[a]+cnt1[a]>cnt0[b]+cnt1[b];
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if(y)cnt0[x]++;
            else cnt1[x]++;
            sa[i]=i;
        }
        while(!q.empty())q.pop();
        sort(sa+1,sa+n+1,cmp);
        int now=1,ans=0,num=0;
        for(int i=n;i>=1;i--)
        {
            while(cnt0[sa[now]]+cnt1[sa[now]]>=i)
            {
                q.push(cnt0[sa[now]]);
                now++;
            }
            if(q.empty())continue;
            int v=q.top();
            q.pop();
            ans+=i;
            num+=min(v,i);
        }
        printf("%d %d\n",ans,num);
        for(int i=1;i<=n;i++)cnt0[i]=cnt1[i]=0;
    }
    return 0;
}