uva 11997——K Smallest Sums

喜欢ヅ旅行 2022-08-21 04:17 18阅读 0赞

题意：给定k个含k个数的数列，然后每次从每个序列中取出一个相加，然后问所有的数中前k小的。

思路：将每个表排序后然后插入优先队列中，依次是a\[0\]+b\[0\],a\[0\]+b\[1\],然后不断合并到一张表中，最后打印出来即可。

code：

#include <bits/stdc++.h>
    using namespace std;
    struct node
    {
        int s,b;
        node (int s,int b):s(s),b(b){}
        bool operator < (const node& a) const {
        return s>a.s;
        }
    };
    
    void merge(int *A,int *B,int *C,int n){
        priority_queue<node>q;
        for (int i=0;i<n;i++)
            q.push(node(A[i]+B[0],0));
        for (int i=0;i<n;i++){
            node t=q.top();q.pop();
            C[i]=t.s;
            int b=t.b;
            if (b<n-1) q.push(node(t.s-B[b]+B[b+1],b+1));
        }
    }
    const int N=756;
    int v[N],p[N];
    int main()
    {
        int n;
        while (~scanf("%d",&n)){
            for (int i=0;i<n;i++){
                for (int j=0;j<n;j++)
                    scanf("%d",v+j);
                sort (v,v+n);
                memcpy(p,v,sizeof(v));
                if (i!=0) merge(p,v,p,n);
            }
            printf("%d",p[0]);
            for (int i=1;i<n;i++)
                printf(" %d",p[i]);
            puts("");
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，18人围观）

还没有评论，来说两句吧...

相关阅读

相关 786. K-th Smallest Prime Fraction

786. K-th Smallest Prime Fraction [https://www.cnblogs.com/grandyang/p/9135156.html][ht

- 日理万妓/ 2023年06月03日 15:55/ 0 赞/ 12 阅读

相关 [leetcode]373. Find K Pairs with Smallest Sums -- JavaScript代码

先上代码，这段js代码执行的效率还是比较高的～ / @param {number[]} nums1 @param {number[]} nums2 @param

悠悠/ 2022年09月24日 08:29/ 0 赞/ 114 阅读

相关 leetcode 373. Find K Pairs with Smallest Sums | 373. 查找和最小的K对数字（小根堆）

题目 [https://leetcode.com/problems/find-k-pairs-with-smallest-sums/][https_leetcode.co

水深无声/ 2022年08月30日 15:52/ 0 赞/ 158 阅读

相关 uva 11997——K Smallest Sums

题意：给定k个含k个数的数列，然后每次从每个序列中取出一个相加，然后问所有的数中前k小的。思路：将每个表排序后然后插入优先队列中，依次是a\[0\]+b\[0\]

喜欢ヅ旅行/ 2022年08月21日 04:17/ 0 赞/ 19 阅读

相关 uva 11536——Smallest Sub-Array

题意：给定n个数，这n个数在m的范围之内。v\[i\]=(v\[i-1\]+v\[i-2\]+v\[i-3\])%m+1; 然后求一个最短连续子序列使得序列内包括1-k个数

淡淡的烟草味﹌/ 2022年08月09日 16:44/ 0 赞/ 94 阅读

相关 ACM UVA 11536 Smallest Sub-Array

UVA 11536 Smallest Sub-Array ![20170729102151741][] 题目大意：输入N,M,K，按照规律%M得到数组长度为N的数组，

╰+哭是因爲堅強的太久メ/ 2022年06月11日 03:37/ 0 赞/ 103 阅读

相关 UVa10791 - Minimum Sum LCM （分解因数）

输入n，求两个正整数，是他们的最小公倍数为n，并且是其中最小的一组，输出他们的和。唯一分解定理 n=ap1 \ bp2 \ cp3…… 任何一个大于1的自然数 N,如果

Love The Way You Lie/ 2022年06月08日 10:09/ 0 赞/ 180 阅读

相关 leetcode 373. Find K Pairs with Smallest Sums 暴力循环求解

You are given two integer arrays nums1 and nums2 sorted in ascending order and an intege

蔚落/ 2022年06月07日 02:47/ 0 赞/ 140 阅读

相关【LeetCode】373. Find K Pairs with Smallest Sums

373. Find K Pairs with Smallest Sums You are given two integer arrays nums1 and nums2

深碍√TFBOYSˉ_/ 2022年04月17日 05:29/ 0 赞/ 168 阅读

相关 Uva11997 K Smallest Sums（优先队列）

题意：有一个k\k 的方阵，让你从当中每一行挑选一个数字相加最后能得到K^K次方的和，输出其中最小的k个。分析：《训练指南》P190，先对每一行排序然后两两归并，每

短命女/ 2021年12月11日 12:39/ 0 赞/ 232 阅读