题目描述

本题除【数据范围与约定】外与 合并果子合并果子合并果子，洛谷P1090 完全一致。 

(我太懒了~~~链接麻烦点下进去看，谢谢)

【提示】

- 请注意常数因子对程序效率造成的影响。
- 请使用类型合适的变量来存储本题的结果。
- 本题输入规模较大，请注意数据读入对程序效率造成的影响。

注意洛谷时间限制！！！

输入

输入的第一行是一个整数 n，代表果子的堆数。
输入的第二行有 n 个用空格隔开的整数，第 i 个整数代表第 i 堆果子的个数 ai​。

输出

 输出一行一个整数，表示最小耗费的体力值。

数据规模

【数据规模与约定】

本题采用多测试点捆绑测试，共有四个子任务。

• Subtask 1（10 points）：1≤n≤8。
• Subtask 2（20 points）：1≤n≤103。
• Subtask 3（30 points）：1≤n≤105。
• Subtask 4（40 points）：1≤n≤107。

对于全部的测试点，保证 1≤ai​≤105。

样例输入输出

输入：     输出：

3              15
1 2 9 

思路：

原题我已经写过了(使用的是priority_queue)，见我的文章：但是！！！

时间复杂度 太！！！！！！！！高！！！！！！！！了！！！！！！！！

是O(n log n)，n<=10^7，所以我们把他扔了

换桶排序及双队列！

STEP 1:定义 L 为 long long 类型，方便后续使用(如果用int会WA，因为n10^7，ai每个10^5,那就是10^12,必须long long)

STEP 2:声明桶排序数组和双队列

STEP 3:声明快速读入函数，不然TLE。通过逐字符读取输入，跳过非数字字符，将数字字符转换为整数。(x << 1) + (x << 3) 等价于 x * 10，(ch ^ 48) 将字符转换为数字(P.S.通常位运算要比乘法更快一点点)

STEP 4:输入，将桶数组 a 中的果子堆按重量从小到大加入队列 q1。

STEP 5:开始合并果子堆：

• 使用双队列 q1 和 q2 进行合并：

  • q1 存储原始果子堆。

  • q2 存储合并后的果子堆。

• 每次从 q1 和 q2 中选择最小的两个堆合并：

  • 如果 q1 的堆更小或 q2 为空，则从 q1 中取堆。

  • 否则，从 q2 中取堆。

• 将合并后的堆加入 q2，并累加体力消耗到 sum。

STEP 6: 输出总的体力消耗 sum。

代码

#include<bits/stdc++.h>
using namespace std;
#define L long long
L a[100005],sum,x,y,n;
queue<L>q1,q2;
inline L read()
{
    L x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        int x;
        x=read();
        a[x]++;
    } 
    for(int i=1;i<=100000;i++)
    {
        while(a[i]--)
        {
            q1.push(i);
        }
    }   
    for(int i=1;i<n;i++)
    {
        if((q1.front()<q2.front()&&!q1.empty())||q2.empty())
        {
            x=q1.front();
            q1.pop();
        }
        else
        {
            x=q2.front();
            q2.pop();
        }
        if((q1.front()<q2.front()&&!q1.empty())||q2.empty())
        {
            y=q1.front();
            q1.pop();
        }
        else
        {
            y=q2.front();
            q2.pop();
        }
        sum+=x+y;
        q2.push(x+y);
    } 
    cout<<sum;
    return 0;
}

运行结果