精华内容
下载资源
问答
  • 合并果子

    2021-02-13 17:33:11
    合并果子 题目描述 在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量...

    合并果子

    题目描述

    在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

    每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过 (n1)(n - 1) 次合并之后, 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

    因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 11,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。

    Link

    O(nlogn)O(n\log n)

    #include<iostream>
    #include<algorithm>
    #include<queue>
    #include<cstdio>
    #define ll long long
    using namespace std;
    
    priority_queue<ll,vector<ll>,greater<ll> >q;
    
    int main()
    {
        int n;
        cin>>n;
        while(n--)
        {
            ll x;
            scanf("%lld",&x);
            q.push(x);
        }
        ll ans=0;
        while(q.size()>=2)
        {
            ll _=q.top();
            q.pop();
            ll __=q.top();
            q.pop();
            ans+=_+__;
            q.push(_+__);
        }
        cout<<ans<<endl;
        return 0;
    }
    

    加强版

    做完之后我们发现还有一道加强版,这个数据范围看 O(nlogn)O(n\log n) 的算法就不行了。
    时间都去哪了?我们发现不少时间耗费在队列中插入新元素。那么如果合并之后的果子不加入原有的序列,而是另起炉灶,那么每一次合并,两个序列中的较小值与次小值合并。原序列是有序的,而新序列中合并出的果子,先合并的一定比后合并的小,也就是说,也是有序的。
    那么最后,你看这个 aia_i 这么小,一定是桶排,那就变成 O(n)O(n) 的复杂度。

    Code

    #include<iostream>
    #include<algorithm>
    #include<queue>
    #include<cstdio>
    #define ll long long
    using namespace std;
    
    queue<ll>q1,q2;
    int t[100010];
    
    int read()
    {
    	int x=0;
    	char c=getchar();
    	while(c<'0'||c>'9')
    	{
    		c=getchar();
    	}
    	while(c>='0'&&c<='9')
    	{
    		x=x*10+c-'0';
    		c=getchar();
    	}
    	return x;
    }
    
    ll get()
    {
        ll _,__;
        if(q1.empty())
        {
            _=q2.front();
            q2.pop();
            return _;
        }
        if(q2.empty())
        {
            _=q1.front();
            q1.pop();
            return _;
        }
        _=q1.front(),__=q2.front();
        if(_<__)
        {
            q1.pop();
            return _;
        }
        q2.pop();
        return __;
    }
    
    int main()
    {
        int n;
        n=read();
        while(n--)
        {
            int _;
            _=read();
            t[_]++;
        }
        ll ans=0;
        for(int i=1;i<=100000;i++)while(t[i]--)q1.push((ll)(i));
        while(q1.size()+q2.size()>=2)
        {
            // puts("Amazing!");
            ll _,__;
            _=get();
            __=get();
            ans+=_+__;
            q2.push(_+__);
        }
        printf("%lld",ans);
        return 0;
    }
    

    彩蛋

    在这里插入图片描述
    Amazing!

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,621
精华内容 648
关键字:

合并果子