UESTC 1599 wtmsb【优先队列+排序】

题目链接:UESTC 1599 wtmsb

题意:给你一组数,每一次取出两个最小的数,将这两个数的和放入这组数中,直到这组数只剩下一个,求最后剩下那个数的大小!

分析:比赛的时候首先我就看到这道题数据是200000,跑时100ms,我把思路捋了一遍,然后讲给旁边人听,一眼看过去,lfh说用哈夫曼树吧,然后找了个板子直接扔上去了,

结果显示出这样的操作:Restricted Function on test 1,从来没见过这个错误啊,百度找了一下,发现这个错误是它oj本身不支持某些函数,比如qsort这种排序操作,wc。。。有毒吧!然后气炸的我扔了一个sort排序,这回总应该过了吧,Time Limit Exceeded on test 1,好的吧,这个怕是有毒哦,后来稳了下yzx,他说优先队列+排序可过,我问:时间复杂度呢!然后,,,,他说不知道,随便搞搞就过了!这TM也行?看来要好好学数据结构了!

优先队列+排序的做法就是取出队头的两个数,然后把它们的和推入到这个队列中,然后优先队列会自动进行排序操作,所以你就能每一次取出两个最小的数,然后推入这两个数的和到队列中去,时间复杂度估计不会超过O(n)(毕竟只有100ms啊,大概也就只能跑1e7的数据)

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=200020;
 4 int main()
 5 {
 6     int n;
 7     cin>>n;
 8     priority_queue<int, vector<int>, greater<int> >q;
 9     for(int i=0;i<n;i++)
10     {
11         int x;
12         cin>>x;
13         q.push(x);
14     }
15     int sum,ans=0;
16     while(1)
17     {
18         int head1=q.top();
19         q.pop();
20         int head2=q.top();
21         q.pop();
22         sum=head1+head2;
23         ans=ans+sum;
24         if(q.empty())
25             break;
26         q.push(sum);
27     }
28     cout<<ans<<endl;
29     return 0;
30 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

[编程题] 猜数游戏分析代码

首先我们分析,dp[i]表示前i个数的合法个数 当第i个数是素数的时候,前面除了1都没有能除尽的,所以这个位置可以随便选Y或N,所以dp[i] = dp[i-...

1233
来自专栏数据之美

Java 正则表达式 StackOverflowError 问题及其优化

正则可以看做一门 DSL,但它却应用极其广泛,可以轻松解决很多场景下的字符串匹配、筛选问题。同时呢有句老话: “ 如果你有一个问题,用正则表达式解决,那么你现在...

4317
来自专栏take time, save time

你所能用到的数据结构(九)

十二、为了count的最终胜利 在介绍完最基本的堆栈模型之后,下面要继续的是第二种最基本的模型,队列。队列,在现实生活中经常可以看到(不过考虑到在我国大部分人...

2907
来自专栏木可大大

编写优雅代码的最佳实践

Robert Martin曾说过"在代码阅读中说脏话的频率是衡量代码质量额唯一标准"。同时,代码的写法应当使别人理解它所需的时间最小化,也就是说我们写的代码是给...

1012
来自专栏C语言及其他语言

[每日一题]C语言程序设计教程(第三版)课后习题5.7

题目描述 给出一个不多于5位的整数,要求 1、求出它是几位数 2、分别输出每一位数字 3、按逆序输出各位数字,例如原数为321,应输出123 输入 一个不大于5...

3527
来自专栏技术沉淀

Pandas雅虎金融数据获取与分析

4133
来自专栏java达人

哈希表

哈希表是种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希表时,它的优点多得让人难以置信。不论哈希表中有多少数据,插入和删除(有时包括侧除)只需要接...

1907
来自专栏ATYUN订阅号

PyTorch 4.0版本迁移指南

欢迎阅读PyTorch 0.4.0的迁移指南。在此版本中,我们引入了许多振奋人心的新功能和重要的bug修复,旨在为用户提供更好,更清晰的接口。在这个指南中,我们...

1692
来自专栏C/C++基础

基数排序简介及其并行化

  基数排序号称线性时间排序算法中性能最好,速度最快的排序算法。本文将简要概括其算法思想,串行代码及其并行化。

1451
来自专栏猿人谷

oc 中随机数的用法(arc4random() 、random()、CCRANDOM_0_1()

1)、arc4random() 比较精确不需要生成随即种子        使用方法 :                  通过arc4random() 获取0到...

2428

扫码关注云+社区

领取腾讯云代金券