加强版:合并果子[NOIP2004]
2024-10-20 23:24:32
题目
链接：https://ac.nowcoder.com/acm/contest/26887/1001
来源：牛客网时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld题目描述
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
输入描述:
输入包括两行，第一行是一个整数n(1<＝n<=10000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai(1<＝ai<=20000)是第i种果子的数目。
输出描述:
输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。
示例1
输入
3
1 2 9
输出
15
备注:
对于30％的数据，保证有n<=1000：
对于50％的数据，保证有n<=5000；
对于全部的数据，保证有n<=10000。
题解
1.贪心
每一次合并最小的两堆果子
2.实现方法
1)使用两个单调栈(O(n))
2)使用二叉堆(优先队列) (O(log2 N))
一.使用STL//注意:默认是大根堆,有两种解决办法:一种是使用相反数,第二种是利用语法规则改变排序的使用
转载自:https://blog.csdn.net/S_999999/article/details/88555829
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct cmp{ bool operator () ( int r , int l ){
return r > l;
}
};
struct cmp1{
bool operator ()( int a ,int b ){
return a<b;
}
};
int main(void){ // priority_queue< int > q;// 默认是 从大到小。
// priority_queue < int , vector<int> ,less<int> > q;//从大到小
// priority_queue < int , vector<int>, greater<int> > q; //从小到大，需要vector
// priority_queue < int , vector<int> , cmp1 > q;//从大到小，需要vector
// priority_queue < int , vector<int> , cmp > q;//从小到大，需要vector
q.push( 1 );
q.push( 2 );
q.push( 3 ); while( !q.empty() ){
int t =q.top();
q.pop();
printf("%d ",t); }
return 0;
}
//有没有发现重载操作符的时候比sort更加少
二.自己设计一颗树(注意:比赛可以使用STL)
在这里的误区:在制造容器的时候进行了一次复制,但是没有及时更正不一样的地方
#include <iostream>
#include <algorithm>
#include <utility>
#include <string_view>
using namespace std;
int q[10010];//这里写的是小根堆,最上面是q[1]
int cnt = 0;
inline void mswap(int& x, int& y)
{
int tmp = x;
x = y;
y = tmp;
}
inline void pop()
{
q[1] = q[cnt];
cnt--;
int m = 1;
int n = m * 2;//注意底下要在两个儿子之间做出选择
if (n + 1 <= cnt && q[n + 1] < q[n])
n++;
while (n <= cnt && q[m] > q[n])
{
mswap(q[m], q[n]);
m = n;
n = m * 2;//注意底下要在两个儿子之间做出选择
if (n + 1 <= cnt && q[n + 1] < q[n])
n++;
}
}
inline void push(int x)
{
cnt++;
q[cnt] = x;
int m = cnt;
int n = cnt / 2;
while (n && q[m] < q[n])
{
mswap(q[n], q[m]);
m = n;
n = n / 2;
}
}
inline int top()
{
return q[1];
}
代码
代码一(使用自己写的二叉堆)
#include <iostream>
#include <algorithm>
#include <utility>
#include <string_view>
using namespace std;
int q[10010];//这里写的是小根堆,最上面是q[1]
int cnt = 0;
inline void mswap(int& x, int& y)
{
int tmp = x;
x = y;
y = tmp;
}
inline void pop()
{
q[1] = q[cnt];
cnt--;
int m = 1;
int n = m * 2;//注意底下要在两个儿子之间做出选择
if (n + 1 <= cnt && q[n + 1] < q[n])
n++;
while (n <= cnt && q[m] > q[n])
{
mswap(q[m], q[n]);
m = n;
n = m * 2;//注意底下要在两个儿子之间做出选择
if (n + 1 <= cnt && q[n + 1] < q[n])
n++;
}
}
inline void push(int x)
{
cnt++;
q[cnt] = x;
int m = cnt;
int n = cnt / 2;
while (n && q[m] < q[n])
{
mswap(q[n], q[m]);
m = n;
n = n / 2;
}
}
inline int top()
{
return q[1];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int ans = 0;
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
int tmp;
cin >> tmp;
push(tmp);
}
for (int i = 0; i < n - 1; i++)
{
int t1, t2;
t1 = top();
pop();
t2 = top();
pop();
ans += t1 + t2;
push(t1 + t2);
}
cout << ans;
return 0;
}
代码二(使用STL容器)注意我这里是最伟大的自定义函数
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct cmp
{
bool operator()(int x, int y)
{
return x > y;
}
};
priority_queue<int, vector<int>, cmp >q;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int ans = 0;
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
int tmp;
cin >> tmp;
q.push(tmp);
}
for (int i = 0; i < n - 1; i++)
{
int t1, t2;
t1 = q.top();
q.pop();
t2 = q.top();
q.pop();
ans += t1 + t2;
q.push(t1 + t2);
}
cout << ans;
return 0;
}
代码三(使用了单调栈)[最快的代码!!!]
参考:https://www.luogu.com.cn/blog/171554/solution-p6038
基本思想:没有必要把所有的数据按顺序都放到一起,按照顺序放到两处也不是不可以!!!
顺便再带一个桶排序,更快!!
#include <iostream>
#include <queue>
#define MAX 10010
using namespace std;
queue<int>q1;
queue<int>q2;
int to[MAX];
int main()
{
int ans = 0;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int tmp;
cin >> tmp;
to[tmp] ++;
}//进行桶排序
for (int i = 0; i < MAX; i++)
{
while (to[i])
{
to[i]--;
q1.push(i);
}
}
for (int i = 0; i < n - 1; i++)
{
int a, b;
if (q1.empty() || !q2.empty() && q2.front() < q1.front())
{
a = q2.front();
q2.pop();
}
else
{
a = q1.front();
q1.pop();
}
if (q1.empty() || !q2.empty() && q2.front() < q1.front())
{
b = q2.front();
q2.pop();
}
else
{
b = q1.front();
q1.pop();
}
ans += a + b;
q2.push(a + b);
}
cout << ans;
return 0;
}
最新文章
- Java学习之注解Annotation实现原理
- Day10-线程进程
- 排列组合算法的javascript实现
- 使用AutoMapper进行对象间映射
- jQuery原生框架-----------------核心框架
- IOS开发 strong，weak，retain，assign，copy nomatic 等的区别与作用
- Win10开发究竟能实现哪些牛逼的功能
- nginx按天切割日志
- Java中可变长参数的使用及注意事项
- TOAD FOR MYSQL 进行数据插入时乱码的解决办法---MariaDB 5.5
- 【VB6 学习文档管理系统源码】
- LinkedIn高级分析师王益：大数据时代的理想主义和现实主义（图灵访谈）
- 【JQuery学习历程】2.JQuery选择器
- winform 之1---窗体介绍
- SVN的命令解析(感觉不错就转了)
- NEO从入门到开窗(3) - NEO编译器
- "ORA-20100: 为 FND_FILE 创建文件 o0003167.tmp 失败"
- SEO常用命令大全
- [编译] 2、minGW gcc在windows搭建编译win32程序环境
- Javascript高级编程学习笔记（10）—— 作用域、作用域链