begin

P6033 [NOIP 2004 提高组] 合并果子 加强版

思路

题目也说了，这是 P1090 的加强版，只变了数据范围，也就是说思路是一样的。

正常的贪心思路是每次取最少的两堆果子进行合并，合并 $n-1$ 轮，然后输出。

那么这个思路正常的代码应该都会用 sort 和 priority_queue，但是这两个时间复杂度都是 $O(n \log n)$ 的，无法通过。

sort

我们发现这题 $a_i$ 的值域只有 $10^5$，于是我们就想到可以用 $O(n)$ 的桶排代替 $O(n \log n)$ 的 sort。

priority_queue

我们可以通过两个 queue 来代替一个 priority_queue。

因为我们每次取的都是最小的两个，那么全排序一遍显然有点浪费时间。我们只需要两个“单调队列”，每次取的最小的两个肯定就出自于 $Q1_1,Q1_2,Q2_1,Q2_2$ 之中，这样我们就可以用 $O(1)$ 的判断来代替 $O(\log n)$ 的排序。

但是如何保证两个队列是单调的呢？

很简单，我们把排序结果放在 $Q1$ 中，把后续所有的合并结果扔到 $Q2$ 中。

But why?

首先 $Q1$ 不难想，因为它开局就是单调的，它在后面又是一个只出不进的角色，所以他一定是单调的。

然后就是 $Q2$，不难发现每次合并的体力值是在单调递增的，因为如果当前需要耗费的体力比上一次小，那么你在上一次就可以有更优的选择，那答案就一定更小。

至此，我们已经成功完成了一个 $O(n)$ 的算法来通过此题。

Code

#include <bits/stdc++.h>
#define ll long long // 不开 long long 见祖宗
#define ull unsigned long long
#define db double
#define ldb long double
#define gc() getchar()
#define pc(a) putchar(a)
#define sqrt(a) __builtin_sqrt(a)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a/__gcd(a,b)*b
#define y1 fuck_cmath
using namespace std;
const int M=1e5+10;
ll read()
{
	ll x=0;
	bool bo=0;
	char ch=gc();
	while (!isdigit(ch)) bo|=(ch=='-'),ch=gc();
	while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=gc();
	return bo?-x:x;
} // 快读
void write(ll x)
{
	if (x<0) pc('-'),x=-x;
	if (x>9) write(x/10);
	pc(x%10+'0');
} // 快写（其实没必要）
ll n,a,ans,t[M],maxn,x,y;
queue<ll> q1,q2;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    n=read();
    for (ll i=1;i<=n;i++)
    {
        a=read();
        t[a]++; // 桶排
        maxn=max(maxn,a);
    }
    // 排序结果放进 Q1
    for (ll i=1;i<=maxn;i++) while (t[i]--) q1.push(i);
    for (ll i=1;i<n;i++)
    {
        if (q2.empty() || (!q1.empty() && q1.front()<q2.front()))
        {
            x=q1.front();
            q1.pop();
        }
        else
        {
            x=q2.front();
            q2.pop();
        }
        if (q2.empty() || (!q1.empty() && q1.front()<q2.front()))
        {
            y=q1.front();
            q1.pop();
        }
        else
        {
            y=q2.front();
            q2.pop();
        }
        // 取最小值
        ans+=x+y;
        q2.push(x+y); // 合并结果放到 Q2
    }
    write(ans);
    return 0;
}

end