POJ3253 Fence Repair(贪心)

切割木板的顺序是自由的，所以每次选择两块最短的板，组合在一起，加入队列，原来两个板出队，直到队列中为空或者只剩下一个板时结束。这里使用优先队列较为方便。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #define ll __int64 using namespace std; int len[20005]; int main() { //freopen("d:\\test.txt","r",stdin); int n; ll ans=0; cin>>n; priority_queue
       
        ,greater
        
          >q;//最小元素在队头 for(int i=0;i
         
          >len[i]; q.push(len[i]); } while(!q.empty()) { int t1=q.top(); q.pop(); if(!q.empty()) { int t2=q.top(); q.pop(); ans+=t1+t2; q.push(t1+t2); } else break; } printf("%I64d\n",ans); return 0; }