(UVa 11997)K Smallest Sums --多路归并问题,优先队列

2024-02-05 02:48

本文主要是介绍(UVa 11997)K Smallest Sums --多路归并问题,优先队列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:
http://acm.hust.edu.cn/vjudge/problem/18702

题意:
有k个数组,每个数组k个元素。在每个数组中取一个元素加起来,有k^k个和。求这些和中最小的k个(重复的值算多次)?

分析:
我们先来求两个元素个数为n的且有序的数组A,B的前n个最小值。组合情况有n*n种,但是我们可以我这些和组织成如下有序表:
表1:A1+B1<=A1+B2<=A1+B3<=……
表2:A2+B1<=A2+B2<=A2+B3<=……
表3:A3+B1<=A3+B2<=A3+B3<=……
…..
表n:An+B1<=An+B2<=An+B3<=……
求这些数的前n个最小值,是多路归并的问题。
利用优先队列,每次队列里有每张表的最小的值,然后从这些之中取出最小值,然后将取出最小值的那张表的下一个值入队列。依次取n次即可。
其中第a张表的元素形式如Aa+Bb。我们可以用二原组(s,b)来表示,其中s=Aa+Bb。我们可以不用存a,因为如果我们需要得到元素(s,b)在a表中的下一个元素(s’,b+1),经过计算s’=s-Bb+Bb+1。并不需要知道a。
元素的结构体如下:

struct Item
{int s,b;Item(int s,int b):s(s),b(b){};// s=A[a]+B[b]。这里的a并不重要,因此不保存bool operator < (const Item& rhs)const {return s>rhs.s;}
};

两个元素个数为n的数组中求前n个最小值的函数为:

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]}}
}

所以在求k个数组时只需要k-1次调用即可。
由于再读入A[]后,以后的计算里面都是通过s-B[]来计算A[]的值的,所以我们可以将每次的结果存入在A中。也不用一个二维数组存所有的值,可以不断的使用一个一维数组即可

AC代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;const int maxn=800;
int a[maxn],b[maxn];struct Item
{int s,b;Item(int s,int b):s(s),b(b){};// s=A[a]+B[b]。这里的a并不重要,因此不保存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]}}
}int main()
{int n;while(scanf("%d",&n)==1){for(int i=0;i<n;i++)scanf("%d",&a[i]);sort(a,a+n);for(int i=1;i<n;i++){for(int j=0;j<n;j++){scanf("%d",&b[j]);}sort(b,b+n);merge(a,b,a,n);// 两两合并}printf("%d",a[0]);for(int i=1;i<n;i++)printf(" %d",a[i]);printf("\n");}return 0;
}

这篇关于(UVa 11997)K Smallest Sums --多路归并问题,优先队列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/679541

相关文章

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

关于MongoDB图片URL存储异常问题以及解决

《关于MongoDB图片URL存储异常问题以及解决》:本文主要介绍关于MongoDB图片URL存储异常问题以及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录MongoDB图片URL存储异常问题项目场景问题描述原因分析解决方案预防措施js总结MongoDB图

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Mysql如何解决死锁问题

《Mysql如何解决死锁问题》:本文主要介绍Mysql如何解决死锁问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录【一】mysql中锁分类和加锁情况【1】按锁的粒度分类全局锁表级锁行级锁【2】按锁的模式分类【二】加锁方式的影响因素【三】Mysql的死锁情况【1

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr