POJ 2442 Sequence

24002 ワード

問題を解くデータ構造——データ構造データ構造——二叉山

テーマ

  m   ，    n     。
                       m      。
   ，        n^m     ，                   ，   n^m  。
                n  。
    
         T，              。
     T     。
        ，         m n。
   m   m     ，          10000。
    
        ，           n    ，         。
       。

サンプル入力

サンプル出力

3 3 4

問題を解く

は、m m m行n n列の1つの数行列が、行ごとに1つの数を引き出して同じ列にすることができるという意味です.n m n^m nm種の組み合わせがあり、これらの組み合わせの中から、最小のn n n n n nとの組み合わせ

が見出されます.

行数が2行2行以上の場合、1行目と2行目の和を比較して、1行目に小さいものを置いて、1行目を優先列

に押し込む.

行数が1行だけの場合は、この操作を行わずに、第1行の数を優先列

に直接押し込む.

がドッキングした第2行からm m m行に優先列を入力し、優先列をクリアします.a aは大きいものから小さいものまでです.その後、次の遍歴は逆遍歴して、その行の最初の数とaは全ての数を優先列に押し込みます.a a aの中の各数と加算して、優先キューより最大の要素が小さいと、一番大きな要素がポップアップされ、最大の要素より大きいと、b r e a k break breakは、次の行の数

までジャンプします.

S T＿L＿STL＿STL優先キュー会T＿L＿E TLE＿TLEは、その後、手書きヒープ

に変更された.
コード

#include 
using namespace std;
const int maxn = 3e3 + 100;

template <typename T>
inline void Read(T &s) {
    s = 0;
    T w = 1, ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch))  { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
    s *= w;
}

template <typename T>
inline void Write(T s) {
    if (s < 0) putchar('-'), s = -s;
    if (s > 9) Write(s / 10);
    putchar(s % 10 + '0');
}

namespace MakeHeap {
    int size, heap[maxn];
    
    inline void Swap(int &aa, int &bb) { aa ^= bb ^= aa ^= bb; }
    
    inline void Up(int p) {
        while (p > 1) {
            if (heap[p] > heap[p >> 1]) {
                Swap(heap[p], heap[p >> 1]);
                p >>= 1;
            }
            else break;
        }
    }
    
    inline void Insert(int val) {
        heap[++size] = val;
        Up(size);
    }
    
    inline int GetTop() { return heap[1]; }
    
    inline void Down(int p) {
        int s = p * 2;
        while (s <= size) {
            if (s < size && heap[s] < heap[s + 1]) ++s;
            if (heap[s] > heap[p]) {
                Swap(heap[s], heap[p]);
                p = s, s = p * 2;
            }
            else break;
        }
    }
    
    inline void Extract() {
        heap[1] = heap[size--];
        Down(1);
    }
}
using namespace MakeHeap;

int t, n, m, x;
int a[maxn];

int main() {
    Read(t);
    while(t--) {
        Read(m), Read(n);
        for (int i = 1; i <= m; ++i) {
            if (i == 1) {
                for (int j = 1; j <= n; ++j) {
                    Read(x), Insert(x);
                }
            }
            
            else {
                for (int j = 1; j <= n; ++j) {
                    a[j] = GetTop(); 
                    Extract();
                }
                
                for (int j = 1; j <= n; ++j) {
                    Read(x);
                    
                    for (int k = n; k >= 1; --k) {
                        if (j == 1) {
                            Insert(a[k] + x);
                        }
                        else {
                            if (a[k] + x <= GetTop()) {
                                Insert(a[k] + x);
                                Extract();
                            }
                            else break;
                        }
                    }
                }
            }
        }
        
        for (int i = n; i >= 1; --i) {
            a[i] = GetTop();
            Extract();
        }
        
        for (int i = 1; i <= n; ++i) {
            Write(a[i]), putchar(' ');
        }
        puts("");
    }
    return 0;
}

データ構造-キューの順番待ち