首页 > 代码库 > Fence Repair

Fence Repair

2024-07-12 22:38:44   226人阅读

　　有n(n>=1&&n<=20000)个木棒。现在要将这些木棒还原为一根。每次只能将两根连接成一根。费用为这两根的长度。求还原的最小费用。

　　输入：n,接下来n个正整数，代表长度。

　　输出最小费用。

#include"iostream"#include"cstdio"#include"cstring"using namespace std;__int64 node[20054];void heap(int i){    int left=i*2,right=i*2+1,mins=i;    if(left<=node[0]&&node[left]<node[mins])        mins=left;    if(right<=node[0]&&node[right]<node[mins])        mins=right;    if(i!=mins)    {        swap(node[i],node[mins]);        heap(mins);    }}void inheap(__int64 key){    node[++node[0]]=key;    int i=node[0];    while(i>1&&node[i]<node[i/2])    {        swap(node[i],node[i/2]);        i/=2;    }}__int64 get(){    __int64 p=node[1],q;    node[1]=node[node[0]];    node[0]--;    heap(1);    q=node[1];    node[1]=node[node[0]];    node[0]--;    heap(1);    inheap(q+p);    return p+q;}int main(){    int n,i,j;    while(cin>>n)    {        node[0]=0;        for(i=1;i<=n;i++)        {            cin>>node[i];            inheap(node[i]);        }        __int64 ans=0;        for(i=1;i<n;i++)            ans+=get();        cout<<ans<<endl;    }    return 0;}


联系
我们