学步园

STL
heap应用

题目：http://poj.org/problem?id=2442

题目大意：给出一个n×m的矩阵，从没一行拿出一个组成新的序列，

则一共有n^m方个序列，输出这n^m序列中序列和最小的前m个序列的和。

思路：要求的是最小的前n个和，所以想到可能维护n个数据就够了，而且也觉得用这n

个里的最大值来当拦路虎。
但是还是没想到怎么解。
最后看了别人的阶梯报告。忽然大悟。

可以两行两行处理，步骤：

1:将第一行放入sum[m]数组中并排序；

2:将下一行row[]
，用第0个元素与sum[0..m - 1]相加并放到temp[0..m-1]
中

3：利用temp建立大根堆

4：对于前行的第1到m-1个元素i，枚举sum[0..m-1]并相加，

  

即x=row[i] +
sum[j]，当x》temp[0]即堆顶时，枚举结束，考虑i+1

5：将temp升序放入sum中

6：循环2，3，4，5直到第n行

什么时候我能自己想到呢！！！！！！！

提交情况：wa
1次

数组开小了

#include
<cstdio>

#include
<cstring>

#include
<algorithm>

using namespace std;

#define MAXN 110

#define MAXM 2010

int n, m;

int ans[MAXM];

int temp[MAXM];

int row[MAXM];

int main(){

        
int CASE, i, j, k, x;

        
scanf("%d", &CASE);

        
while(CASE --){

                  
scanf("%d %d", &n, &m);

                  
for(i = 0; i < m; ++ i) scanf("%d",
&ans[i]);

                  
sort(ans, ans + m);

                  
for(i = 1; i < n; ++ i){

                           
for(j = 0; j < m; ++ j) scanf("%d",
&row[j]);

                           
for(j = 0; j < m; ++ j) temp[j] = ans[j] +
row[0];

                           
make_heap(temp, temp + m);

                           
for(j = 1; j < m; ++ j){

                                    
for(k = 0; k < m; ++ k){

                                              
x = ans[k] + row[j];

                                              
if(x >= temp[0]) break;

                                              
pop_heap(temp, temp + m);

                                              
temp[m - 1] = x;

                                              
push_heap(temp, temp + m);

                                    
}

                           
}

                           
sort_heap(temp, temp + m);

                           
for(j = 0; j < m; ++ j) ans[j] = temp[j];

                  
}

                  
for(j = 0; j < m - 1; ++ j) printf("%d ",
ans[j]);

                  
printf("%d\n", ans[m - 1]);

        
}

        
return 0;

}