你需要动态维护插入值以及求最小值和次小值,因此你选择堆(
by Zpair @ 2023-03-20 19:08:45
@[Zpair](/user/163337) 有没有一种可能,他压根不知道堆是干什么的。
by Mysterious_Cat @ 2023-03-20 19:11:26
仔细康康[时间限制](https://www.luogu.com.cn/problem/P1090)
800ms好吧
by _Adolf_Hitler_ @ 2023-03-20 19:18:06
```cpp
#include <iostream>
using namespace std;
int heap[30001];
int heap_size,n;
void swap(int &a,int &b)
{
int t=a;
a=b;
b=t;
}
int get()
{
int son,pa,res;
res=heap[1];
heap[1]=heap[heap_size--];
pa=1;
while(pa*2<=heap_size)
{
son=pa*2;
if(son<heap_size&&heap[son+1]<heap[son])
son++;
if(heap[pa]<=heap[son])
break;
else
swap(heap[pa],heap[son]);
pa=son;
}
return res;
}
void put(int d)
{
int son,pa;
heap[++heap_size]=d;
son=heap_size;
while(son>1)
{
pa=son>>1;
if(heap[son]>=heap[pa])
break;
swap(heap[son],heap[pa]);
son=pa;
}
}
void work()
{
int x,y;
int ans=0;
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>x;
put(x);
}
for(int i=1;i<n;i++)
{
x=get();
y=get();
ans+=x+y;
put(x+y);
}
cout<<ans<<endl;
}
int main()
{
work();
return 0;
}
```
###### 不用堆用什么?sort啊?算法标签:贪心,堆,优先队列
by _Adolf_Hitler_ @ 2023-03-20 19:21:36
@[NNNNzh](/user/614984)
by _Adolf_Hitler_ @ 2023-03-20 19:22:14
@[Zpair](/user/163337) 哦哦我大概懂了,动态维护
by NNNNzh @ 2023-03-20 20:41:02
@[JODAN_POOLE](/user/931106) ok谢谢
by NNNNzh @ 2023-03-20 20:41:18