首页 > 代码库 > uva 11997 （基础数据结构）

uva 11997 （基础数据结构）

2024-07-08 10:54:06   225人阅读

题意： 有一个k*k 的方阵，让你从当中每一行挑选一个数字相加最后能得到K^K次方的和，输出其中最小的k个。

思路：先对每一行排序然后两两归并，每次取前k个再和下一行再进行归并。在归并的时候用一个优先队列维护最大的k个值每次先放k个进去然后一次每行和队顶比较，若是小则替换否则break最后输出即可。

代码如下：

 1 #include <stdio.h> 2 #include <algorithm> 3 #include <iostream> 4 #include <queue> 5 #include <set> 6 #include <string.h> 7 #include <map> 8 #include <vector> 9 #include <string>10 #include <math.h>11 using namespace std;12 13 const int LEN = 2010;14 int Num[LEN][LEN];15 int s[LEN], n;16 17 void Merge(int a, int b){18     int top = 0;19     priority_queue<int> q;20     for(int i=0; i<n; i++){21         q.push(Num[a][i] + Num[b][0]);22     }23     for(int i=0; i<n; i++){24         for(int j=1; j<n; j++){25             int ls = Num[a][i] + Num[b][j];26             int nv = q.top(); q.pop();27             if(nv > ls){ 28                 swap(nv, ls);29                 q.push(nv);30             }else {31                 q.push(nv);32                 break;33             }34         }35     }36     while(!q.empty()){37         s[top++] = q.top();q.pop();38     }39     for(int i=top-1, j=0; i>=0; i--, j++){40         Num[b][j] = s[i];41     }42 }43 44 int main()45 {46 //    freopen("in.txt","r",stdin);47     //freopen("out.txt","w",stdout);48 49     ios::sync_with_stdio(false);50     while(cin >> n){51         for(int i=0; i<n; i++){52             for(int j=0; j<n; j++){53                 cin >> Num[i][j];54             }55             sort(Num[i], Num[i]+n);56         }57         for(int i=1; i<n; i++){58             Merge(i-1, i);59         }60         for(int i=n-1; i>=0; i--){61             cout << s[i];62             if(i != 0) cout << ‘ ‘;63         }cout << endl;64     }65     return 0;66 }
View Code

 


联系
我们