优先队列 POJ 3253 Fence Repair-白红宇

优先队列 POJ 3253 Fence Repair

阅读量：5922 次

发布时间：2019-06-19

本文共 1156 字，大约阅读时间需要 3 分钟。

题意：一块木板按照某个顺序切成a[1], a[2]...a[n]的长度，每次切都会加上该两段木板的长度，问选择什么顺序切能使得累加和最小

分析：网上说这是。很容易想到先切掉最长的，反过来也就是相当于每次取最短的两块合并成一块，直到最后剩下原来的一块，优先队列实现

代码：

/************************************************* Author        :Running_Time* Created Time  :2015/9/14 星期一 08:51:15* File Name     :POJ_3253.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 2e4 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;int a[N];int main(void) { int n; while (scanf ("%d", &n) == 1) { for (int i=1; i<=n; ++i) scanf ("%d", &a[i]); priority_queue

, greater

> Q; for (int i=1; i<=n; ++i) Q.push (a[i]); ll ans = 0; while (Q.size () > 1) { int l1 = Q.top (); Q.pop (); int l2 = Q.top (); Q.pop (); ans += l1 + l2; Q.push (l1 + l2); } printf ("%I64d\n", ans); } return 0;}

转载于:https://www.cnblogs.com/Running-Time/p/4806277.html

你可能感兴趣的文章