P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G 题解

OyamaMahiro_Kawaii · 2023-02-12 18:02:26 · 个人记录

难度：普及/提高-

考点：贪心，模拟

这是一道非常经典的题目，在提高组和USACO都出现过。就算没有做过原题也多半做过它的变种，所以理解原题就显得至关重要。

题意给出n个数，每一次加和会使两个数变成一个，同时获得两个数和的代价。可以看出，最后所有数会合并为一个数，求合并成一个数后代价的最小值。

显然，先合并的数为最后损失贡献最多的倍数，所以使损失最小，要让最小的数最先合并，所以排序数组。

分成两个数组进行合并，因为空数组被赋予最大值所以优先合并给出数组。

将合并后的和插入空数组末尾继续合并。

暴力乱搞时间复杂度O(n^2)，而标程是O(n)的

#include<bits/stdc++.h>
#define int long long
#define M 100010
using namespace std;
int n,cnt,a1[M],a2[M],ans;
signed main()
{
    ios::sync_with_stdio(0);
    memset(a1,127,sizeof(a1));
    memset(a2,127,sizeof(a2));
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a1[i];
    sort(a1+1,a1+n+1);
    int i=1,j=1,w;
    for(int k=1;k<n;k++)
    {
        w=a1[i]<a2[j] ? a1[i++] : a2[j++];
        w+=a1[i]<a2[j] ? a1[i++] : a2[j++];
        a2[++cnt]=w;
        ans+=w;
    }
    cout<<ans;
    return 0;
}

对于更加简便的优先队列做法，时间复杂度O(nlogn)

#include<bits/stdc++.h>
#define int long long
#define M 100010
using namespace std;
int n,x,y,ans;
priority_queue<int,vector<int>,greater<int> > a;
signed main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>x,a.push(x);
    while(a.size()!=1){
        x=a.top();
        a.pop();
        y=a.top();
        a.pop();
        ans+=x+y;
        a.push(x+y);
    }
    cout<<ans;
    return 0;
}