首页 > 其他分享 >P1631 序列合并

P1631 序列合并

时间:2024-02-13 09:33:05浏览次数:32  
标签:10 int 合并 cin pop P1631 ++ push 序列

题目链接:

第一时间想到的思路是将 \(a,b\) 数组中的 \(n^2\) 个和全部枚举并压入优先队列中,最后再输出前 \(n\) 个数,代码如下:

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N], b[N];

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) cin >> b[i];
	
	priority_queue<int, vector<int>, greater<int> > p;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int x = a[i] + b[j];
			p.push(x);
		}
	}
	for (int i = 0; i < n; i++) {
		cout << p.top() << " ";
		p.pop();
	}
	return 0;
}

但这样的话由于 \(N\) 最大可取 \(10^5\),优先队列会内存超限
image

于是想到动态维护 \(n\) 个从小到大的和,用大根堆,先压满 \(n\) 个和,由于 \(a,b\) 均为单调不减的数列,如果新的和比当前堆顶元素还要大,说明接下来也一定比堆顶元素大,直接break掉从 \(a\) 数组的下一轮循环开始枚举;反之若新的和比当前堆顶元素小,则pop掉一个元素再加入当前这个新的元素,大根堆会自动将其排序。

以下是AC代码。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N], b[N], res[N];
priority_queue<int> p;

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) cin >> b[i];
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int x = a[i] + b[j];
			if (p.size() < n) p.push(x);
			else {
				if (p.top() > x) {
					p.pop();
					p.push(x);
				}
				else break;//很重要,如去掉这行则会有三个点超时
			}
		}
	}
	for (int i = 0; i < n; i++) {
		res[i] = p.top();
		p.pop();
	}
	for (int i = n - 1; i >= 0; i--) cout << res[i] << " ";
	return 0;
}

标签:10,int,合并,cin,pop,P1631,++,push,序列
From: https://www.cnblogs.com/pangyou3s/p/18014356

相关文章

  • 【C++】给定两个增序的链表,试将其合并成一个增序的链表。
    给定两个增序的链表,试将其合并成一个增序的链表。#include<iostream>#include<stack>usingnamespacestd;structListNode{intval;ListNode*next;ListNode(intx):val(x),next(nullptr){}};voidprintList(ListNode*head){while(head){std:......
  • 我在代码随想录|写代码| 贪心算法 | 理论基础, 455.分发饼干, 376. 摆动序列,53. 最大
    学习目标:博主介绍:27dCnc专题:数据结构帮助小白快速入门......
  • 洛谷 P1795 无穷的序列 题解
    题目传送门题目大意:给定整数\(a\),判断\(a\)是否属于数列\(1,2,4,7,11\cdots\)。多测。1.暴力枚举(90pts)不难发现,该数列除第一项外第\(n\)项比第\(n-1\)项多\(n-1\)。故暴力枚举\(n\),计算数列的每一项,判断是否与\(a\)相等,大于\(a\)就break。多测加记忆化,用mx......
  • PHP项目&变量覆盖&反序列化&未授权访问&身份验证
    CNVD拿1day-验证&未授权-xhcms&Bosscms此种漏洞由于没有什么关键函数,所以需要通过功能点去进行测试。Bosscms未授权访问CNVD官网上搜索Bosscms未授权访问漏洞。根据描述,影响的是1.0版本。看到发送时间为21年12月29好,收录时间为22年1月18号。再去官网看版本更新的时间点,V1.0版......
  • 力扣递归之88. 合并两个有序数组
    给你两个按非递减顺序排列的整数数组 nums1和nums2,另有两个整数m和n,分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中,使合并后的数组同样按非递减顺序排列。注意:最终,合并后数组不应由函数返回,而是存储在数组nums1中。为了应对这种情况,nums1的初......
  • 力扣递归之21. 合并两个有序链表
    将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例1:输入:l1=[1,2,4],l2=[1,3,4]输出:[1,1,2,3,4,4]示例2:输入:l1=[],l2=[]输出:[]示例3:输入:l1=[],l2=[0]输出:[0]classSolution{publicListN......
  • 43、excel快速填充序列号,删除行时序号自动跟上
    平时填充序号的做法:首先在第1、2行输入1、2,然后用手往下拖动,填充后面的行,缺点:当我删除一行时,后面的序号不会自动按顺序填充上 解决方法:1、在excel上选中A6单元格,然后左上角输入A6:A110,按【回车】键2、直接输入【=ROW()-1】,再按【ctrl+回车】键盘就可以了缺点:由于公......
  • JavaScript 实现类似SQL 左联接式的对象数组合并
    在JavaScript中,你可以使用对象合并(Objectmerging)来模拟数据库的左联接操作。左联接操作会将两个对象的特定属性进行合并,类似于SQL中的LEFTJOIN操作。假设你有两个对象,每个对象代表一个表:consttable1=[{id:1,age:30},{id:3,age:25},];consttable2......
  • 反序列化漏洞
    反序列化漏洞什么是序列化、反序列化例子引入序列化是将对象的状态信息转换为可以存储或传输的形式的过程。在序列化期间,对象将当前状态写入到临时或持久性存储区。以后,可以通过从存储区中读取或反序列化对象状态,重新创建该对象。简单的来讲:(含例子easy.php)序列化:把对象转换......
  • Jackson序列化clob数据
    1.情景展示在java当中,有时候我们不得不用jdbc来读取数据库数据,而不是通过mybatis框架。这样就遇到一个问题:如果表字段的数据类型为clob时,使用springboot默认进行序列化时,会报错。如何解决?2.具体分析在springboot中,其默认的序列化类时Jackson。既然Jackson的默认序列化规......