POJ3253Fence Repair（优先队列或单调队列）

经典题目了，大意是说如果要切断一个长度为a的木条需要花费代价a，问要切出要求的n个木条所需的最小代价。

无论是以下哪种方法，最原始的思路就是从相反的角度思考，将每两个合并，花费的代价是他们两个的和，一直到最后只剩下一个

方法一：

使用STL的priority_queue，先将所有的木条放入到队列中。每次取出两个木条将他们的长度相加，加入到花费当中去，然后放回到队列中。

这样计算的时间复杂度就是O(NlogN)。

方法二：

使用单调队列，我们可以分析到，由于每次取出的都是优先队列中最小的两个，也就是首部的两个，那我们可以考虑另外借用一个数组b用来存放每次取出的两个数的和，我们注意到，每次取出来的两个数相加，得到的和也是单调递增的（这个很容易证明），可以看下面的例子：

原始状态：

a 1 3 5 6 7 8 9

b null

第一次在a里取出两个数1,3相加，放入b中：

a 5 6 7 8 9

b 4

这里我们先从a、b两个数组队首取出一个最小的数4,再从两个数组的队首取出一个最小的数（此时b数组已经队空）5，相加后放入b：

a 6 7 8 9

b 9

同理，这次会取出6和7，相加放入b（注意每次相加的结果都是放入b中的，这里不放入a中是为了保证a和b数组的单调性）：

a 8 9

b 9 13

经过几次操作后会得到：

a null

b 39

最后a队列空，b队列只剩下一个数，这时合并就结束了

我们可以注意到，由于每次都将相加得到的和放进了b队列，所以b一定是单调递增的，而且最后平均每个数只被使用了一次，所以它的复杂度是O(N)的。

单调队列和优先队列：

POJ3253Fence Repair（优先队列或单调队列）

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

 #define lson k<<1, L, mid

 #define rson k<<1|1, mid+1, R

 typedef long long LL;

 const double eps = 1e-;

 const int MAXN = ;

 const int MAXM = ;

 int main()

 {

     int N, len;

     while(~scanf("%d", &N))

     {

         priority_queue<LL, vector<LL>, greater<LL> >q;

         for(int i=;i<N;i++)

         {

             scanf("%d", &len);

             q.push((LL)len);

         }

         LL ans = ;

         while(q.size() > )

         {

             LL p = q.top(); q.pop();

             p += q.top();    q.pop();

             ans += p;

             q.push(p);

         }

         printf("%lld\n", ans);

     }

     return ;

 }

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

 #define lson k<<1, L, mid

 #define rson k<<1|1, mid+1, R

 typedef long long LL;

 const double eps = 1e-;

 const int MAXN = ;

 const int MAXM = ;

 LL a[MAXN], b[MAXN];

 int main()

 {

     int N;

     while(~scanf("%d", &N))

     {

         mem0(b);

         for(int i=;i<N;i++) scanf("%lld", &a[i]);

         sort(a, a+N);

         int frontA=, frontB=, rearB=, num=;

         LL ans=;

         while(++num<N)

         {

             int sum = ;

             if(frontB==rearB || (frontA<N&&a[frontA]<b[frontB])) { sum += a[frontA]; frontA ++; }

             else { sum += b[frontB]; frontB++; }

             if(frontB==rearB || (frontA<N&&a[frontA]<b[frontB])) { sum += a[frontA]; frontA ++; }

             else { sum += b[frontB]; frontB++; }

             b[rearB++] = sum;

             ans += sum;

         }

         printf("%lld\n", ans);

     }

     return ;

 }

秒客网

POJ3253Fence Repair（优先队列或单调队列）

相关文章