【洛谷P1090】合并果子

合并果子

题目链接

贪心：每次先合并最小的两堆果子

用堆实现

 #include<iostream>

 #include<cstdio>

 using namespace std;

 int heap_size,n;

 int heap[];

 void swap(int &a,int &b)

 {

     int t=a;a=b;b=t;

 }

 void put(int d)

 {

     int now,next;

     heap[++heap_size]=d;

     now=heap_size;

     while(now>)

     {

         next=now>>;

         if(heap[now]>=heap[next]) return;

         swap(heap[now],heap[next]);

         now=next;

     }

 }

 int get()

 {

     int now,next,res;

     res=heap[];

     heap[]=heap[heap_size--];

     now=;

     while(now<<<=heap_size)

     {

         next=now<<;

         if(next<heap_size&&heap[next+]<heap[next]) next++;

         if(heap[now]<heap[next]) return res;

         swap(heap[now],heap[next]);

         now=next;

     }

     return res;

 }

 void work()

 {

     int i,x,y,ans=;

     cin>>n;

     for(i=;i<=n;i++)

     {

         cin>>x;

         put(x);

     }

     for(i=;i<n;i++)

     {

         x=get();

         y=get();

         ans+=x+y;

         put(x+y);

     }

     cout<<ans<<endl;

 }

 int main()

 {

     ios::sync_with_stdio(false);

     work();

     return ;

 }

手写堆真恶心。。

STL是个好东西

 #include<iostream>

 #include<queue>

 #include<cstdio>

 using namespace std;

 priority_queue<int,vector<int>,greater<int> >h;

 int n,x,ans=,tmp=;

 int main() {

     scanf("%d",&n);

     for(int i = ; i <= n; i++) {

         scanf("%d",&x);  h.push(x);

     }

     for(int i = ; i <= n-; i++) {

         tmp = h.top( );

         h.pop( );

         tmp = tmp+h.top( );

         h.pop( );

         h.push(tmp);

         ans += tmp;

     }

     printf("%d",ans);

     return ;

 }