[NOIP2004]合并果子

简介: [NOIP2004]合并果子

题目: [NOIP2004]合并果子 ,哈哈,我们今天来看一道比较简单的题嘛,这是选自NOIP上的一道题,好了,我们一起来看看题意吧:

考虑到直接复制题目,或者截屏的方式不是很方便阅读,我就把直接题目链接放下面!

题目传送门: [NOIP2004]合并果子

思路:

我们用两个队列,一个队列装已经排好序的元素,一个队列装合并后的元素,然后我们取出队头小的一个并出队,然后我们取出队头小的一个并出队,然后把取出的两个元素相加,加入到合并元素的队列中去!具体的我们直接看代码!

我们来看看成功AC的代码吧:

#include<bits/stdc++.h>
using namespace std;
int n;
int a[10010];
queue<int> q1,q2;//用两个队列,方便理解
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++) q1.push(a[i]);
    int ans=0;
    for(int i=1;i<n;i++){
        int x[3];
        for(int j=1;j<=2;j++){//找到队头小的
            if(q2.empty()||!q1.empty()&&q1.front()<q2.front()){
                x[j]=q1.front(); q1.pop();
            }else{
                x[j]=q2.front(); q2.pop();
            }
        }
        ans+=x[1]+x[2];
        q2.push(x[1]+x[2]);
    }
    cout<<ans;
    return 0;
}


相关文章
|
3天前
[NOIP2002]过河卒 标准递归
[NOIP2002]过河卒 标准递归
20 6
|
7天前
|
算法 C++
【洛谷 P1090】[NOIP2004 提高组] 合并果子(贪心算法+哈夫曼编码+优先队列)
该编程题目要求设计算法,将不同种类的果子合并成一堆,使得消耗的体力最小。给定果子种类数`n`(1至10000)和每种果子的数量,需输出合并的最小体力值。使用优先队列(最小堆),每次取出两个数量最少的果子堆合并,并更新总体力消耗。样例输入为3种果子(1, 2, 9),输出最小体力耗费为15。提供的AC代码采用C++实现,通过优先队列优化合并顺序。
8 0
|
7天前
【洛谷 P1002】[NOIP2002 普及组] 过河卒 题解(递归+记忆化搜索)
`NOIP2002`普及组的过河卒问题是一个棋盘路径计数挑战。卒从$(0,0)$出发到$(n,m)$,只能向下或向右移动,马在$(c1,c2)$固定,控制某些点。任务是计算不受马阻挡的路径数。输入是目标和马的位置,输出是路径总数。使用动态规划和记忆化搜索避免重复计算,样例输入$(6,6,3,3)$输出$6$。代码中定义了$f(x,y)$计算$(x,y)$处的路径数,利用边界条件和递推关系计算。
8 0
|
1月前
|
JavaScript
线性dp之石子合并
线性dp之石子合并
|
1月前
|
人工智能
合并果子(哈夫曼树)NOIP2004提高组
合并果子(哈夫曼树)NOIP2004提高组
|
1月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-936 砝码称重
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-936 砝码称重
34 0
|
11月前
|
人工智能 算法 C++
洛谷 P1090 合并果子(贪心)
洛谷 P1090 合并果子(贪心)
106 0
|
11月前
|
人工智能
1369:合并果子(fruit)
1369:合并果子(fruit)
|
11月前
|
机器学习/深度学习 人工智能
1320:【例6.2】均分纸牌(Noip2002) 2020-11-30
1320:【例6.2】均分纸牌(Noip2002) 2020-11-30