搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > money哥的C > 使用优先队列(红黑树)找最小匹配

使用优先队列(红黑树)找最小匹配

money哥的C 2018-06-28

Problem K

K Smallest Sums

You're given k arrays, each array has k integers. There are kk ways to pick exactly one element in each array and calculate the sum of the integers. Your task is to find the k smallest sums among them.

Input

There will be several test cases. The first line of each case contains an integer k (2<=k<=750). Each of the following k lines contains k positive integers in each array. Each of these integers does not exceed 1,000,000. The input is terminated by end-of-file (EOF). The size of input file does not exceed 5MB.

Output

For each test case, print the k smallest sums, in ascending order.

Sample Input

3

1 8 5

9 2 5

10 7 6

2

1 1

1 2

Output for the Sample Input

9 10 12

2 2

 

题意:每行选一个加在一起,则总共有k^k个和,求前k小的值都是多少。

解析:如果排序的话必然超时。所以算法就是先把每行都升序排好,两行两行的求前k小的值,求出来后赋值入数组再继续求下去。即分成a0+b0,a0+b1,a0+b2,,,;a1+b0,a1+b1,,,;a2+b0,a2+b1,a2+b2;则最小的值一定在a0+b0,a1+b0,a2+b0,,,之间,例如最小的为a1+b0,那么就把它踢出队列,在加入队列a1+b1,继续上述操作,直到找出前k小。

#include<stdio.h>  

#include<string.h>  

#include<queue>  

#include<algorithm>  

#define INF 800  

using namespace std;  

  

struct numt  

{  

    friend bool operator < (numt n1,numt n2)//优先队列比较结构的固定模版  

    {  

        return n1.sum > n2.sum;//此处>代表从小到大排列,若为<则是从大到小  

    }  

    int sum,n;  

};  

int k,num[INF][INF];  

int ans[INF];  

  

void fx(int *a,int *b)  //a,b两个数列求前k最小值  

{  

    priority_queue<numt>Q;  

    int cnt = 0;  

    numt temp;  

    for(int i = 0; i < k ; i ++) //先赋初始值  

    {  

        temp.sum = a[i]+b[0];  

        temp.n = 0;  

        Q.push(temp);  

    }  

    for(int i = 1; i < k ; i ++)  

    {  

        numt t1 = Q.top();  

        Q.pop();  

        a[i-1] = t1.sum ;       //最小的都赋给a,因为a在后面都没用到了,直接赋值  

        t1.sum = t1.sum+b[t1.n+1]-b[t1.n];  

        t1.n ++;  

        Q.push(t1);  

    }  

    a[k-1] = Q.top().sum;  

}  

  

int main()  

{  

    while(scanf("%d",&k) != EOF)  

    {  

        for(int i = 0 ; i < k ; i ++)  

        {  

            for(int j = 0 ;j < k ; j++)  

            {  

                scanf("%d",&num[i][j]);  

            }  

            sort(num[i],num[i]+k);  //一定要先排序好  

        }  

        for(int i = 1; i < k ; i ++)  

        {  

            fx(num[0],num[i]);  

        }  

        printf("%d",num[0][0]);  

        for(int i = 1 ; i < k; i ++)  

            printf(" %d",num[0][i]);  

        printf("\n");  

    }  

    return 0;  

}  


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《使用优先队列(红黑树)找最小匹配》的版权归原作者「money哥的C」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注money哥的C微信公众号

money哥的C微信公众号:gh_82f3d67fc187

money哥的C

手机扫描上方二维码即可关注money哥的C微信公众号

money哥的C最新文章

精品公众号随机推荐