146. 序列

2024-04-01 05:04

文章标签 序列 146

本文主要是介绍146. 序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

有t个测试用例。

每个测试用例，包含m个数组，每个数组包含n个数字。你可以从每个数组里面选择一个数字，然后将m个数字加和得到一个数字。用这样的方式一共可以获得n的m次幂个数字。问，在这么多个数字中选出最小的n个数字。

思路：

老规矩，我们还是先看一下最笨的做法是什么。那就是将所有的组合全部遍历得到，然后选出最小的n个数字。

然后你就会发现，这么多个数字，开不了这么大的内存将他们存下来。那怎么办呢？

你就会想到一个只有n个空间的数组不就行了，先用第一排的第一个数字，加上第二排的n个数字，得到了最初的n个数字。然后，你就发现没有然后了。因为下一步你就不知道怎么做了。

因为第一排的那个数字，你不知道他在第一排里面是多大，所以和第二排加和后你也不知道这些数字和第一排其他数字加上第二排相比是怎样的个大小关系。

那这里你就会想到，我把第一排先排个序，再和第二排进行加和，那这次得到的n个数字不就是a0为基础的n个数了么。但这时还是有个问题，就是最小的数肯定是这两排里面所有加和数字的最小，但是第二小并不一定存在在这里面。也就是说倒数第二小的数字可能不是a0加上第二排的数字得到的。

所以这时候你就需要一个操作，假设说a0 + bi 是最小值，那倒数第二小是哪个数呢？
就是a1+bi 么？

不一定，应该是a1+bi 和a0+{b0~bn}（除bi外）所有数比较之后的那个最小值。

好，按照这个操作，假设a1+bi 和a0加其他数比较后确实是最小值，那倒数第三小的值是什么呢？

没错，就是a2+bi和a0+{b0~bn}（除bi外）所有数比较之后的那个最小值。假设a0+bj 是倒数第三小的值，那倒数第四小的值是什么呢？

思考一下

没错，就是a0+{b0~bn}（除bi ， bj外）和a2+bi 和 a1+bj 比较之后的那个最小值。

好的，相信到这里，你已经明白了两个序列得到最小的n个值的做法。那问题来了，题目要求的是m个序列的最小的n个值，这可怎么办呢？？

我相信你已经有了答案。就是按照上面的做法，两两进行比较就可以得到了啊！！！

如果你没想明白，那我就稍微点拨你一下。当你用上面的做法，可以得到 n 个最小的数字，这是没有问题的吧。然后，这 n 个数字，不就相当于你已经排好序的从小到大的第一排数字嘛，你接下来得到的第三排序列，不就相当于刚刚第二排的序列嘛？这不又是一个两两序列求最小的n个值的问题了嘛！！！！

ok，话不多说，上代码


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;typedef pair<int , int> PII;int n , m;
int a[N] , b[N] , c[N];void merge(){priority_queue<PII , vector<PII> , greater<PII>> heap;//定义一个小根堆，里面的元素都是按照第一个元素从小到大排列的//里面元素是{x,y}，x是a[i]+b[j]，y是ifor(int i = 0 ; i < n ; i++){heap.push({a[0] + b[i] , 0});}//首先用最小的数字加上b排数字，放入小根堆中for(int i = 0 ; i < n ; i++){auto t = heap.top();heap.pop();int s = t.first , p = t.second;//取出当前最小的值，s是值的大小，t是a的下标ic[i] = s;//将最小的值先保存在c数组中heap.push({s-a[p]+a[p+1] , p+1});//将a[i+1]+b[j]放入小根堆中，继续跟其他数比大小，p从i变成i+1}for(int i = 0 ; i < n ; i++)a[i] = c[i];//将临时数组c的值赋值给a，a里面就是每次两两序列比较后从小到大排序的最小n个数
}int main(){int t;cin >> t;while(t--){cin >> m >> n;//得到第一排序列for(int i = 0 ; i < n ; i++)scanf("%d",&a[i]);sort(a , a+n);for(int i = 0 ; i < m-1 ; i++){//接下来的每排序列都当作第二排for(int j = 0 ; j < n ; j++)scanf("%d" , &b[j]);merge();//两个序列进行比较，得到n个最小值}for(int i = 0 ; i < n ;  i++){printf("%d ",a[i]);}puts("");}return 0;
}