我希望你是我独家记忆

一段永远封存的记忆,随风而去
posts - 263, comments - 31, trackbacks - 0, articles - 3
   :: 首页 :: 新随笔 ::  :: 聚合  :: 管理

PKU——2442——(堆的题目)

Posted on 2008-08-28 15:38 Hero 阅读(563) 评论(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 ) ;
    
forint 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()
{
    
forint i=2; i<=inm; i++ )
    {
        
forint 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[]指针越界
        forint 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 ;
        
forint 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 ) ;
        forint k=1; k<=inn+1; k++ ) data1[k] = data3[k] ;
    }
}

void output() 
{
    
forint i=1; i<inn; i++ ) printf( "%d ", data1[i] ) ;

    printf( 
"%d\n", data1[inn] ) ;
}

int main()
{
    
while( scanf( "%d"&innum ) != EOF )
    {
        
forint ct=1; ct<=innum; ct++ )
        {
            input() ;

            process() ;

            output() ;
        }
    }

    
return 0 ;
}

Feedback

# re: PKU——2442——(堆的题目)  回复  更多评论   

2011-03-15 21:33 by acmer
谢谢,我用了你的方法过了这道题目!
可以加你QQ吗?
我的QQ是339379406

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理