题解：AT_abc116_d [ABC116D] Various Sushi

· · 题解

题解：AT_abc116_d [ABC116D] Various Sushi

题目Link

思路

考虑贪心。主要难点在于如何平衡美味度和多样性加成。因为多样性加成具有平方级的增长速度，然后动归似乎也做不出来。

考虑用一种替换的思路。用结构体存储数据，然后降序排序。先计算前 k 个数的美味值总和，作为初始值。然后考虑用一个记录数组记录同种类寿司最大的美味值和种类为 i 的寿司出现次数。

因为出现了相同种类的寿司，用一个新种类的寿司替换，显然平方对总美味值的贡献更大。所以，用两个优先队列，分别用一个大根堆 q 记录选中种类的最大美味值，和一个小根堆 r 记录已选中重复种类的寿司。

在记录前 k 数的美味值总和时，如果发现新种类，该种类出现次数增加 1。

然后，那些没被选过且同种类有重复的寿司放入 q 队列，用一个 vec 来记录已选中且同种类有重复的寿司。

然后遍历 vec，如果 vec 中该种类有重复寿司，按美味值降序排序，保留最大值，其他加入可替换堆。

最后贪心替换过程，用新种类替换重复种类，记录最大值。

Code

#include<bits/stdc++.h> 
#define int long long    
using namespace std;     
const int maxn=1e5+10;  
int n,k,cnt[maxn],mx[maxn];
struct node{
    int t,d;
}a[maxn];           
priority_queue<int> q; 
priority_queue<int,vector<int>,greater<int> > r;
bool cmp(node x,node y) 
{
    return x.d>y.d;
} 
int tot,sum1,ans;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i].t>>a[i].d;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++) 
    {
        int tmp=a[i].t;
        if(!mx[tmp]) mx[tmp]=a[i].d; 
    }
    for(int i=1;i<=k;i++) 
    {
        tot+=a[i].d;              
        if(!cnt[a[i].t]) sum1++;    
        cnt[a[i].t]++;            
    }
    for(int i=1;i<=n;i++)
        if(!cnt[i]&&mx[i]) q.push(mx[i]);
    vector<int> vec[maxn];
    for(int i=1;i<=k;i++) 
        vec[a[i].t].push_back(a[i].d);
    for(int i=1;i<=n;i++) 
    {
        if(vec[i].size()>1) 
        {
            sort(vec[i].begin(),vec[i].end(),greater<int>());
            for(int j=1;j<vec[i].size();j++) 
                r.push(vec[i][j]);
        }
    }
    ans=tot+sum1*sum1;
    while(!q.empty()&&!r.empty()) 
    {
        int tmp1=q.top(),tmp2=r.top();  
        tot=tot-tmp2+tmp1;    
        sum1++;          
        q.pop();      
        r.pop();   
        ans=max(ans,tot+sum1*sum1);
    }
    cout<<ans;
    return 0;
}