題意：輸入一個數k（2 <= k <= 750），然後輸入k*k的矩陣，元素為不超過1,000,000的正整數，k行每行取一個數出來相加，求最小的前k個和。 ——>>k個數的和最小，那麼任意兩行的那兩個數的和也最小，否則就可以找到比該值更小的數，所以，可以先求兩行中k個最小和，再進行多路歸並即可。 [cpp] #include <iostream> #include <algorithm> #include <queue> using namespace std; const int maxn = 750 + 10; //每行最多可能有750個數 struct Item //定義結點類型 { int s; //s = A[i] + B[j] int b; //b = j即B[j]的下標 Item(int ss, int bb):s(ss), b(bb){} bool operator < (const Item& e) const //重載運算符，使優先隊列中的元素按s的值從小到大地排 { return s > e.s; } }; void merge(int *A, int *B, int k) //將表A與表B合並，即求當k = 2時的k個最小和 { int i; priority_queue<Item> pq; for(i = 0; i < k; i++) //第一列元素入列 pq.push(Item(A[i]+B[0], 0)); for(i = 0; i < k; i++) //找出k個最小和 { Item item = pq.top(); //取出隊列中最小的 pq.pop(); A[i] = item.s; int b = item.b; if(b+1 < k) //如果不是最後一個，就加入第“1”列的行列中去 pq.push(Item(item.s-B[b]+B[b+1], b+1)); } } int a[maxn][maxn]; //輸入的k*k數組 int main() { int k, i, j; while(cin>>k) { for(i = 0; i < k; i++) { for(j = 0; j < k; j++) cin>>a[i][j]; sort(a[i], a[i]+k); //排個序 } for(i = 1; i < k; i++) merge(a[0], a[i], k); //兩兩合並 for(i = 0; i < k-1; i++) //輸出結果 cout<<a[0][i]<<" "; cout<<a[0][k-1]<<endl; } return 0; }
