【洛谷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 ;
 }