不一样做法的题解

Carey_chen · 2026-02-05 12:48:07 · 题解

这是一道数据结构优化贪心题。

对于 1≤n≤10^5 的数据，使用优先队列，每次弹出最小的两堆果子合并为新的一堆，放回优先队列。

考虑优化这个过程，不难发现，由于每次被合并的两堆果子必然越来越大，每次新的果子堆的大小也必然单调不降。

考虑使用指针和链表来完成，不断向后扫描果堆并插入。

时间复杂度证明

排序使用桶排序，O(n + V)。

每次合并两堆果子，需要扫描链表插入一个新节点，但扫描指针只向后移动，所以每个节点最多被扫描一次。

由于合并 n-1 次，总节点数为 O(n) ，所以总扫描次数为 O(n)。

总时间复杂度 O(n) 。

代码

STL list 常数比较大，要使用手写链表。

一个很丑的实现：

#include <bits/stdc++.h>

using namespace std;

struct List
{
    struct Node
    {
        long long a;
        int l, r;
    };

    int pos = 1, siz = 0, len = 0, back = 0;
    Node a[20000010];

    int begin()
    {
        return pos;
    }

    void insert(int pos, long long x)
    {
        siz++;
        len++;
        a[siz].a = x;
        a[siz].l = a[pos].l;
        a[siz].r = pos;
        a[a[siz].l].r = siz;
        a[pos].l = siz;
    }

    void push_back(long long x)
    {
        len++;
        siz++;
        a[siz].a = x;
        a[siz].l = back;
        if(back != 0)
        {
            a[back].r = siz;
        }
        back = siz;
    }

    long long front()
    {
        return a[pos].a;
    }

    long long front_nxt()
    {
        return a[a[pos].r].a;
    }

    void pop_front()
    {
        len--;
        pos = a[pos].r;
        a[pos].l = 0;
    }

    int size()
    {
        return len;
    }
};

int bkt[100010];
List K;

int read(){...} // 快读

int main() 
{
    // freopen("P6033_3.in", "r", stdin);

    int n;
    long long ans = 0;

    n = read();

    for(int i = 1; i <= n; i++)
    {
        bkt[read()]++;
    }

    for(int i = 1; i <= 100000; i++)
    {
        while(bkt[i] > 0)
        {
            K.push_back(i);
            bkt[i]--;
        }
    }

    auto pos = K.begin(); // pos 的位置是单调不降的
    while(K.size() >= 2)
    {
        long long a = K.front(), b = K.front_nxt();
        long long c = a + b;

        ans += c;

        bool OK = false;
        while(1)
        {
            if(K.a[pos].a > c)
            {
                K.insert(pos, c);
                OK = true;
                break;
            }
            if(K.a[pos].r != 0)
            {
                pos = K.a[pos].r; // 这一句只会执行 O(n) 次
            }
            else
            {
                break;
            }
        }

        if(!OK)
        {
            K.push_back(c);
        }

        K.pop_front();
        K.pop_front();
    }

    printf("%lld", ans);

    return 0;
}