[POJ3253]Fence Repair

题目链接：http://poj.org/problem?id=3253

单调队列和优先队列（哈夫曼编码）分别实现:

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 typedef long long LL;
22 
23 const int maxn = 20010;
24 int n;
25 int ha, hb, rb, cnt;
26 LL a[maxn], b[maxn];
27 LL ans;
28 
29 int main() {
30     // freopen("in", "r", stdin);
31     while(~scanf("%d", &n)) {
32         memset(b, 0, sizeof(b));
33         ha = 0;
34         hb = 0;
35         rb = 0;
36         cnt = 0;
37         ans = 0;
38         for(int i = 0; i <n ; i++) {
39             scanf("%I64d", &a[i]);
40         }
41         sort(a, a+n);
42         while(++cnt < n) {
43             int sum = 0;
44             if(hb == rb || (ha < n && a[ha] < b[hb])) {
45                 sum += a[ha];
46                 ha++;
47             }
48             else {
49                 sum += b[hb];
50                 hb++;
51             }
52             if(hb==rb || (ha < n && a[ha] < b[hb])) {
53                 sum += a[ha];
54                 ha++;
55             }
56             else {
57                 sum += b[hb];
58                 hb++;
59             }
60             b[rb++] = sum;
61             ans += sum;
62         }
63         printf("%I64d
", ans);
64     }
65     return 0;
66 }

单调队列0ms

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 typedef __int64 LL;
22 
23 const int maxn = 20010;
24 int n;
25 priority_queue<LL, vector<LL>, greater<LL> > pq;
26 LL ans;
27 
28 int main() {
29     // freopen("in", "r", stdin);
30     while(~scanf("%d", &n)) {
31         while(!pq.empty())    pq.pop();
32         ans = 0;
33         LL a;
34         for(int i = 0; i < n; i++) {
35             scanf("%I64d", &a);
36             pq.push(a);
37         }
38         while(n-- > 1) {
39             a = pq.top();
40             pq.pop();
41             a += pq.top();
42             pq.pop();
43             pq.push(a);
44             ans += a;
45         }
46         printf("%I64d
",ans);
47     }
48     return 0;
49 }

STL优先队列32ms