Uva11997 K Smallest Sums（优先队列）

短命女 2021-12-11 12:39 231阅读 0赞

## 题意： 有一个k\*k 的方阵，让你从当中每一行挑选一个数字相加最后能得到K^K次方的和，输出其中最小的k个。 ##

## 分析：《训练指南》P190，先对每一行排序然后两两归并，每次取前k个再和下一行再进行归并。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    
    struct Item {
      int s, b; // s=A[a]+B[b]。这里的a并不重要，因此不保存
      Item(int s, int b):s(s), b(b) { }
      bool operator < (const Item& rhs) const {
        return s > rhs.s;
      }
    };
    
    void merge(int* A, int* B, int* C, int n) {
      priority_queue<Item> q;
      for(int i = 0; i < n; i++)
        q.push(Item(A[i]+B[0], 0));
      for(int i = 0; i < n; i++) {
        Item item = q.top(); q.pop();// 取出A[a]+B[b]
        C[i] = item.s;
        int b = item.b;
        if(b+1 < n) q.push(Item(item.s-B[b]+B[b+1], b+1)); // 加入A[a]+B[b+1]=s-B[b]+B[b+1]
      }
    }
    
    const int maxn = 768;
    int A[maxn][maxn];
    
    int main() {
      int n;
      while(scanf("%d", &n) == 1) {
        for(int i = 0; i < n; i++) {
          for(int j = 0; j < n; j++) scanf("%d", &A[i][j]);
          sort(A[i], A[i]+n);
        }
        for(int i = 1; i < n; i++) // 两两合并
          merge(A[0], A[i], A[0], n); // (*)
    
        printf("%d", A[0][0]); // 输出结果
        for(int i = 1; i < n; i++)
          printf(" %d", A[0][i]);
        printf("\n");
      }
      return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关 uva 11997——K Smallest Sums

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

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

相关 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 阅读

相关优先队列

[点击打开链接][Link 1] include <cstdio> include <cstring> include <algorithm>

柔光的暖阳◎/ 2022年06月17日 05:41/ 0 赞/ 279 阅读

相关 ACM UVA 11536 Smallest Sub-Array

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

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

相关 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 阅读

相关 UVA 12100 Printer Queue(队列，优先队列)

详细题目：https://vjudge.net/problem/UVA-12100 思路：用队列模拟，开一个<pri , pos> 的队列，分别表示任务的优先级

朱雀/ 2022年06月07日 02:26/ 0 赞/ 212 阅读

相关 UVA 136 Ugly Number（优先队列）

题目 Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1,

深藏阁楼爱情的钟/ 2022年06月07日 00:15/ 0 赞/ 166 阅读

相关【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 阅读