[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;
}


相关文章
|
6月前
|
算法 C++
【洛谷 P1090】[NOIP2004 提高组] 合并果子(贪心算法+哈夫曼编码+优先队列)
该编程题目要求设计算法,将不同种类的果子合并成一堆,使得消耗的体力最小。给定果子种类数`n`(1至10000)和每种果子的数量,需输出合并的最小体力值。使用优先队列(最小堆),每次取出两个数量最少的果子堆合并,并更新总体力消耗。样例输入为3种果子(1, 2, 9),输出最小体力耗费为15。提供的AC代码采用C++实现,通过优先队列优化合并顺序。
76 0
|
6月前
【洛谷 P1002】[NOIP2002 普及组] 过河卒 题解(递归+记忆化搜索)
`NOIP2002`普及组的过河卒问题是一个棋盘路径计数挑战。卒从$(0,0)$出发到$(n,m)$,只能向下或向右移动,马在$(c1,c2)$固定,控制某些点。任务是计算不受马阻挡的路径数。输入是目标和马的位置,输出是路径总数。使用动态规划和记忆化搜索避免重复计算,样例输入$(6,6,3,3)$输出$6$。代码中定义了$f(x,y)$计算$(x,y)$处的路径数,利用边界条件和递推关系计算。
75 0
|
6月前
|
存储 C++
【洛谷 P1089】[NOIP2004 提高组] 津津的储蓄计划 题解(循环)
**摘要:** 这是一个关于编程竞赛题目的摘要,题目编号NOIP2004提高组,名为“津津的储蓄计划”。津津每月初从妈妈那里获得300元,需要根据预算决定储蓄。若预计月底有超过或正好100元,她会存储整百金额。如果某月资金不足预算,输出第一个这样的月份加负号;否则,计算年末时津津手中的总金额(储蓄部分加20%)。输入是12个月的预算,输出是一个整数结果。提供的C++代码示例用于处理这个问题,通过迭代计算每个月的资金状况。样例输入和输出展示了不同情况下的结果。
58 0
|
7月前
|
JavaScript
线性dp之石子合并
线性dp之石子合并
|
7月前
|
人工智能
合并果子(哈夫曼树)NOIP2004提高组
合并果子(哈夫曼树)NOIP2004提高组
|
7月前
【每日一题Day167】LC1000合并石头的最低成本 | 区间dp
【每日一题Day167】LC1000合并石头的最低成本 | 区间dp
55 1
【每日一题Day167】LC1000合并石头的最低成本 | 区间dp
|
人工智能 算法 C++
洛谷 P1090 合并果子(贪心)
洛谷 P1090 合并果子(贪心)
137 0
|
人工智能
1369:合并果子(fruit)
1369:合并果子(fruit)
105 0
|
机器学习/深度学习 人工智能
1320:【例6.2】均分纸牌(Noip2002) 2020-11-30
1320:【例6.2】均分纸牌(Noip2002) 2020-11-30
118 0