poj 2442 Sequence (Priority Queue)

　　真郁闷，明明方法是对的，为什么我的代码老是那么的慢。_(:з」∠)_

　　这题要想考虑两列的情况，然后逐列拓展。

代码如下：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <queue>
 6 
 7 using namespace std;
 8 
 9 const int N = 2222;
10 const int Q = N * N;
11 template<class T>
12 struct PriQ {
13     T q[Q];
14     int sz;
15     void clear() { sz = 0;}
16     void up(int k) {
17         while (k > 1) {
18             if (q[k] < q[k >> 1]) swap(q[k >> 1], q[k]);
19             else return ;
20             k >>= 1;
21         }
22     }
23     void push(T x) {
24         q[++sz] = x;
25         up(sz);
26     }
27     void down(int k) {
28         while ((k << 1) <= sz) {
29             if ((k << 1) == sz || q[k << 1] < q[k << 1 | 1]) {
30                 if (q[k << 1] < q[k]) swap(q[k], q[k << 1]);
31                 else return ;
32                 k = k << 1;
33             } else {
34                 if (q[k << 1 | 1] < q[k]) swap(q[k], q[k << 1 | 1]);
35                 else return ;
36                 k = k << 1 | 1;
37             }
38         }
39     }
40     void pop() {
41         q[1] = q[sz];
42         sz--;
43         down(1);
44     }
45     T top() { return q[1];}
46     int size() { return sz;}
47 } ;
48 PriQ<int> pq;
49 int ans[N];
50 //priority_queue<Node> pq;
51 
52 template<class T>
53 void priqcon(T *a, PriQ<T> &b, int sz) {
54     a[0] = 0;
55     for (int i = 1; i <= sz; i++) {
56         a[++a[0]] = b.top();
57         b.pop();
58     }
59 }
60 
61 int rec[N];
62 
63 int main() {
64     int T, n, m, x;
65     scanf("%d", &T);
66     while (T-- && ~scanf("%d%d", &n, &m)) {
67         ans[0] = 1;
68         ans[1] = 0;
69         int mx;
70         for (int i = 0; i < n; i++) {
71             pq.clear();
72             mx = 0;
73             for (int j = 0; j < m; j++) scanf("%d", &rec[j]);
74             sort(rec, rec + m);
75             for (int j = 0; j < m; j++) {
76                 x = rec[j];
77                 for (int k = 1; k <= ans[0]; k++) {
78                     if (pq.sz < m || ans[k] + x < mx) {
79                         pq.push(ans[k] + x);
80                         mx = max(mx, ans[k] + x);
81                     }
82                 }
83             }
84             priqcon(ans, pq, m);
85         }
86         for (int i = 0; i < m; i++) {
87             if (i) putchar(' ');
88             printf("%d", ans[i + 1]);
89         }
90         puts("");
91     }
92     return 0;
93 }

View Code

　　好了，其实做这题并不是我的原意，实际上是为了测试二叉堆有没写错的。

——written by Lyon