Posted on 2008-08-28 15:38
Hero 阅读(560)
评论(1) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
//PKU 2442 Accepted 260K 438MS C++ 2837B
//两个队列--每次只处理两行
//这个题目让我对"堆"有了新的认识--双向映射
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int INF = 100000000 ;
const int size = 2010 ;
int data1[size] ;
int point[size] ;//data1[]的每个元素的指针
int data2[size] ;
int data3[size] ;//保存data1[]和data2[]相加后的最小inn个元素
struct QUE
{
int len ;
int toheap ;
};
struct QUE que[size] ;
//暂存队列--求出data1[]+data2[]和最小的前n个元素--data3-->data1
int cque ;
int heap[size] ;//指向data3[]
int cheap ;
int innum ; int ct ;
int inn, inm ;
int cmp( const void *a, const void *b )
{
return *(int *)a - *(int *)b ;
}
void input()
{
scanf( "%d %d", &inm, &inn ) ;
for( int i=1; i<=inn; i++ )
{
scanf( "%d", &data1[i] ) ; point[i] = 1 ;
}
qsort( data1+1, inn, sizeof(data1[1]), cmp ) ;
data1[inn+1] = INF ;
}
void swap( int &a,int &b )
{
int t = a ; a = b ; b = t ;
}
void moveup( struct QUE *dist, int n )
{//将新加入的点向上移动来维持堆,n表示要向上移动的点的坐标
// while( n&&arry[n]>arry[(n-1)/2] )
while( n&&dist[heap[n]].len<dist[heap[(n-1)/2]].len )
{
swap( dist[heap[n]].toheap,dist[heap[(n-1)/2]].toheap ) ;
swap( heap[n],heap[(n-1)/2] ) ;
n = ( n-1 ) / 2 ;
}
}
void movedown( struct QUE *dist, int n )
{//堆顶改变后，将其向下移动维持堆.n表示堆中元素总数目
int i = 0 ;
while( i+i+1 < n )
{
//if( i+i+2<n&&arry[i+i+2]>arry[i+i+1]&&arry[i+i+2]>arry[i] )
if( i+i+2<n&&dist[heap[i+i+2]].len<dist[heap[i+i+1]].len&&dist[heap[i+i+2]].len<dist[heap[i]].len )
{
swap( dist[heap[i+i+2]].toheap, dist[heap[i]].toheap ) ;
swap( heap[i+i+2],heap[i] ) ;
i = i+i+2 ;
}
//else if( arry[i+i+1] > arry[i] )
else if( dist[heap[i+i+1]].len < dist[heap[i]].len )
{
swap( dist[heap[i+i+1]].toheap, dist[heap[i]].toheap ) ;
swap( heap[i+i+1],heap[i] ) ;
i = i+i+1 ;
}
else break ;
}
}
void process()
{
for( int i=2; i<=inm; i++ )
{
for( int j=1; j<=inn; j++ )
{
scanf( "%d", &data2[j] ) ;
}//下一行数据输入--求两行和最小的前n个元素
qsort( data2+1, inn, sizeof(data2[1]), cmp ) ;
cheap = -1 ; data2[inn+1] = INF ;//为了避免point[]指针越界
for( int k=1; k<=inn; k++ )
{
que[k].len = data1[k] + data2[1] ; point[k] = 1 ;
heap[++cheap] = k ; que[k].toheap = cheap ;//先heap再toheap
}
int temp ;
for( int k=1; k<=inn; k++ )
{
data3[k] = que[heap[0]].len ; //弹出堆顶的元素
point[heap[0]]++ ; //printf( "point[%d]==%d\n", heap[0], point[heap[0]] ) ;
temp = data1[heap[0]]+data2[point[heap[0]]] ;
que[heap[0]].len = temp ;//更新que[]队列的值
movedown( que, cheap+1 ) ;
}//找出和最小的inn个元素
//memcpy( data1, data3, inn+1 ) ;
for( int k=1; k<=inn+1; k++ ) data1[k] = data3[k] ;
}
}
void output()
{
for( int i=1; i<inn; i++ ) printf( "%d ", data1[i] ) ;
printf( "%d\n", data1[inn] ) ;
}
int main()
{
while( scanf( "%d", &innum ) != EOF )
{
for( int ct=1; ct<=innum; ct++ )
{
input() ;
process() ;
output() ;
}
}
return 0 ;
}