AT4774题解

· · 题解

一、前言

经过3天的奋斗和18次提交，我终于 AC 了！为了庆祝自己 AC，我写了这篇题解。

这篇题解是这道题的第一篇题解，也是本蒟蒻的第一篇题解，如果写得不好请见谅，谢谢！

二、题目分析

这道题的正确解法应该是这样的：我们每次要用 C 数组中最大的数字去尽可能地变 A 数组中小的数字，才能使每一次数字变化的收益最大。所以，我们可以在输入后将 A 数组从小到大排序，将 BC 数组（后来我将 B 数组和 C 数组合并成了一个结构体数组。）以 C 为关键字从大到小排序，然后依次进行比较、替换，并计算总和。如果不算排序，该算法的时间复杂度为 O(n)。 具体实现方式见下一节。

三、代码实现

在写这篇题解之前，我比较喜欢“STL 大法”，所以我很快用 multiset 写出了代码：

#include<bits/stdc++.h>
using namespace std;
multiset<int>a;
multiset<int,greater<int> >bc; 
int main()
{
    int n,m,t,b,c;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>t;
        a.insert(t);
    }
    for(int i=0;i<m;i++)
    {
        cin>>b>>c;
        while(b--)
        {
            bc.insert(c);
        }//添加b个c。
    }
    multiset<int>::iterator f,g;
    long long sum=0;
    int len=a.size();
    for(int i=0;i<len;i++)
    {
        f=a.begin();
        g=bc.begin();
        if(*f<*g)//如果bc中的数据比原先大，就替换。
        {
            bc.erase(g);
            sum+=*g;//sum加上新数据。
        }
        else//否则加上原数据。
        {
            sum+=*f;
        }
        a.erase(f);//以后这个数据就没用了，不如删掉，也方便后面的访问。
    }
    cout<<sum;
    return 0;
}

然后满怀信心地交上去——#7测试点 TLE……

几天后我终于恍然大悟：原来，multiset 每添加一个新的值就要排一次序，看起来 O(n)，其实爆炸！

所以我放弃了 STL，把 multiset 换成了数组，在输入后只统一排序一次，并且去掉了替换数据的部分，毕竟我们要的是总和，而不是所有替换后的值。另外，如果替换不成功，就可以直接跳出循环，因为 A 数组中的数会越来越大，而 BC 中 C 的数会越来越小；不过如果这样，那我们需要在最后将未替换的数加到总和里面。

AC code:

#include<bits/stdc++.h>
using namespace std;
long long a[100010];
struct node{
    long long k,v;//此处的k就是题目中的b，v就是c。
}bc[100010];
bool cmp(node a,node b)
{
    return a.v>b.v;
}
int main()
{
    long long n,m;
    cin>>n>>m;
    for(long long i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    for(long long i=0;i<m;i++)
    {
        cin>>bc[i].k>>bc[i].v;
    }
    sort(bc,bc+m,cmp);
    long long f=0,g=0;//f用来记录第一个不需要替换的数字在数组中的下标，g则是用来遍历bc数组的下标变量。
    long long sum=0;
    if(m)
    {
        for(long long i=0;i<n;i++)
        {
            if(a[i]<bc[g].v)//如果可以替换：
            {
                sum+=(long long)bc[g].v;//总和加上新替换的值；
                bc[g].k--;//还可替换的个数-1。
                if(bc[g].k==0)//如果不能继续替换了：
                {
                    g++;//遍历bc数组的下一个值。
                    if(g==m)//如果没有下一个值了：
                    {
                        f=i+1;
                        break;//(1)记录不需替换的数字下标并跳出循环。
                    }
                }
            }
            else
            {
                f=i;
                break;//同(1)。
            }
            if(i==n-1)
            {
                f=n;//为了避免重复计算，和(1)做同样的处理。
            }
        }
    }
    for(long long i=f;i<n;i++)
    {
        sum+=(long long)a[i];//将没有被替换的数加到总和里。
    }
    cout<<sum;
    return 0;
}

四、结语

如果有人想对这篇题解提建议和意见，可以在其他题解中告诉我，我会努力提升我的题解质量的。

谢谢大家！