特殊的数字排序

0特殊的数字排序 - 蓝桥云课

问题描述

小明被挑选去参加一个ACM比赛。他的任务是解决一个很特别的问题:给定一个整数数组,但是只能通过交换任意两个数的方式来排序。听起来很简单对吗?但是这个问题的难点在于,只有某些数字是可以交换的。例如,数字7和数字3可以交换,但是数字5可能不能和任何数字交换。
你的任务是,给定一个整数数组和一个允许交换的数字对列表,找到可能的最大排序数组。
例如,如果我们有一个数组[2, 3, 5, 7]和一个交换列表(3, 7), (5, 2),我们可以先交换3和7得到[2, 7, 5, 3],再交换5和2得到[5, 7, 2, 3],最终得到可能的排序最大的数组。

输入格式
  • 第一行包含一个整数n,(1 ≤ n ≤ 500),表示数组中整数的个数。
  • 第二行包含n个整数a_i,(1 ≤ a_i ≤ 10^9),表示整数数组。
  • 第三行包含一个整数m,(0 ≤ m ≤ 10^3),表示交换列表的对数。
  • 接下来的m行,每行包含两个整数b_ic_i,(1 ≤ b_i, c_i ≤ 10^9),表示可以交换的整数对,题目保证每对整数都存在于数组中。
输出格式

输出一行,包含n个整数,表示最大排序数组。

样例输入
4
2 3 5 7
2
3 7
5 2
样例输出
5 7 2 3
测评数据规模

1 ≤ n ≤ 500,1 ≤ a_i, b_i, c_i ≤ 10^9,0 ≤ m ≤ 10^3。

思路:

并查集

代码:

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
const ll W = 2e6 + 10;
ll n,m;
ll a[W],fa[W];
bool vis[W];
vector <ll> num[W];
ll find(ll i)
{if(fa[i] != i){fa[i] = find(fa[i]);}return fa[i];
} 
void merge(ll u,ll v)
{ll u1 = find(u);ll v1 = find(v);if(u1 != v1){fa[v1] = u1; }
}
bool check(ll u,ll v)
{return find(u) == find(v);
}
int main(void)
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);map<ll,ll> mp;cin >> n ;for(ll i = 1 ; i <= n ; i++)fa[i] = i;for(ll i = 1 ; i <= n ; i++){cin >> a[i];mp[a[i]] = i;//数字对应数组的下标(出现的) }cin >> m;for(ll i = 1 ; i <= m ; i++){ll x,y;cin >> x >> y;if(!check(mp[x],mp[y]))merge(mp[x],mp[y]);}for(ll i = 1 ; i <= n ; i++){num[find(i)].push_back(a[i]);	}for(ll i = 1 ; i <= n; i++){sort(num[i].begin(),num[i].end());}for(ll i = 1 ; i <= n ; i++){if(!num[find(i)].empty()){cout << num[find(i)].back() << " ";num[find(i)].pop_back();	}}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/34738.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

汽车感性负载-智能高边钳位能量计算

随着汽车电子技术的发展&#xff0c;新的电子电气架构下&#xff0c;越来越多的执行部件在车身出现&#xff0c;比如电磁阀、风机、水泵、油泵、雨刮继电器等常用的执行器&#xff0c; 它们一般都表现为感性特点。驱动这些负载的最简单和最常见的方法是将它们连接到高边侧开关(…

量化交易学习笔记02:双均线策略

双均线策略示例 个股&#xff1a;中国平安 回测日期&#xff1a;2022-5-1至2023-5-1 短均线&#xff1a;5天 长无线&#xff1a;10天 代码&#xff1a; def initialize(context):# 初始化此策略# 设置我们要操作的股票池, 这里我们只操作一支股票# """标的&qu…

利用余弦相似度在大量文章中找出抄袭的文章

我前面的2篇文章分别讲了如果利用余弦相似度来判断2篇文章的相似度&#xff0c;来确定文章是否存在抄袭&#xff0c;和余弦相似度的原理&#xff0c;即余弦相似度到底是怎么来判断文章的相似性高低的等等。这一篇再说下&#xff0c;对于文章字数多和大量文章时&#xff0c;如果…

在 Kaggle 中绘制中文乱码解决

在 Kaggle 中绘制中文时&#xff0c;需要设置 Matplotlib 的字体&#xff0c;否则中文会显示为乱码。可以使用 SimHei&#xff08;黑体&#xff09;或 Microsoft YaHei&#xff08;微软雅黑&#xff09;。 解决方案 使用 matplotlib 设置中文字体在 Kaggle 安装 SimHei 字体 …

在 Ubuntu 服务器上使用宝塔面板搭建博客

&#x1f4cc; 介绍 在本教程中&#xff0c;我们将介绍如何在 Ubuntu 服务器 上安装 宝塔面板&#xff0c;并使用 Nginx PHP MySQL 搭建一个博客&#xff08;如 WordPress&#xff09;。 主要步骤包括&#xff1a; 安装宝塔面板配置 Nginx PHP MySQL绑定域名与 SSL 证书…

Linux线程

1.线程概念 在一个程序里的一个执行路线就叫做线程(thread)&#xff0c;更准确定义&#xff1a;线程是一个进程内部的控制序列 进程至少有一个执行路线&#xff0c;线程在进程内部运行&#xff0c;本质是在进程地址空间内运行&#xff0c;在Linux系统中&#xff0c;CPU眼中&a…

【TI MSPM0】GPIO学习

一、文件样例查找 以GPIO软件轮询为例 下面的四个文件夹分别为不同开发环境提供支持 二、工程导入 1.点击file-点击import project 2.点击browse 3.找到对应的文件打开&#xff0c;选择 推荐使用ticlang,能够提供更加优化的效率 点击finish 三、工程学习 1.readme 文件 &a…

二叉树的基本操作与实现:C语言深度剖析

目录 代码整体框架 1. #define _CRT_SECURE_NO_WARNINGS 2. 头文件引入 3. typedef int BTtype; 4. 二叉树节点结构体定义 二叉树的创建 1. BuyNode 函数 2. CreatNode 函数 二叉树的遍历 前序遍历 中序遍历 后序遍历 二叉树属性的计算 节点个…

深入解析 Latent Diffusion Model(潜在扩散模型,LDMs)(代码实现)

深入解析 Latent Diffusion Model&#xff1a;从传统 Diffusion Model 到高效图像生成的进化 近年来&#xff0c;生成模型在图像合成领域取得了显著进展&#xff0c;其中 Diffusion Model&#xff08;扩散模型&#xff0c;DMs&#xff09;以其出色的生成质量和理论上的稳健性逐…

线性回归原理推导与应用(五):波士顿房价预测实战

波士顿房价是一个非常经典的多元线性回归入门案例数据集。波士顿房价预测数据集包含了可能会影响房价的十三个因素&#xff0c;并给出了实际的房价&#xff08;单位为万美元&#xff09; 波士顿房价数据集数据集下载地址&#xff1a;https://www.kaggle.com/datasets/altavish…

基于CATIA二次开发的低音炮腔体容积精准计算技术详解

一、功能概述 本工具通过PySide6与CATIA V5深度集成&#xff0c;实现了低音炮上下腔体内体积的自动化测量系统。系统采用三维实体建模法进行容积计算&#xff0c;相较于传统手工计算方式&#xff0c;精度提升可达0.5%。主要功能模块包括&#xff1a; 壳体特征自动识别动态草图…

向量数据库原理及选型

向量数据库 什么是向量什么是向量数据库原理应用场景 向量数据库的选型主流向量数据库介绍向量数据库对比主流向量数据库对比表 选型建议 什么是向量 向量是一组有序的数值&#xff0c;表示在多维空间中的位置或方向。向量通常用一个列或行的数字集合来表示&#xff0c;这些数…

IE代理切换器v1.2免费版

虽然IE浏览器已经过时了&#xff0c;但很多其他浏览器&#xff0c;比如谷歌浏览器的代理服务器设置&#xff0c;都还是基于IE浏览器来进行设置的&#xff0c;如果你的工作场景需要切换不同的代理服务器来访问网络&#xff0c;那这款工具适合你&#xff0c;目前该工具可以实现IE…

模运算的艺术:从基础到高阶的算法竞赛应用

在算法竞赛中&#xff0c;模运算&#xff08;取模运算&#xff09;是一个非常重要的概念&#xff0c;尤其在处理大数、防止溢出、以及解决与周期性相关的问题时。C 中的模运算使用 % 运算符&#xff0c;但它的行为和使用场景需要特别注意。 1. 模运算的基本概念 模运算是指求一…

SpringBoot前后端不分离,前端如何解析后端返回html所携带的参数

有一个SpringBoot实现的前后端不分离项目&#xff0c;当前端跳转某个界面时&#xff0c;比如下面的菜单树按钮&#xff0c;后端在返回页面menuTree.html时&#xff0c;还携带了一个参数角色roleId&#xff0c;以便打开菜单树&#xff0c;还要根据这个角色查询对应的分配授权的菜…

操作系统八股文整理(一)

操作系统八股文整理 一、进程和线程的区别二、进程与线程的切换过程一、进程切换进程切换的步骤&#xff1a; 二、线程切换线程切换的步骤&#xff1a; 三、进程切换与线程切换的对比四、上下文切换的优化 三、系统调用一、系统调用的触发二、从用户空间切换到内核空间三、执行…

卷积神经网络(CNN)之 EfficientNet

在深度学习领域&#xff0c;模型的计算效率与性能之间的平衡一直是一个核心挑战。随着卷积神经网络&#xff08;CNN&#xff09;在图像分类、目标检测等任务中取得显著成果&#xff0c;模型的复杂度和计算需求也急剧增加。2019年&#xff0c;Google Research 提出的 EfficientN…

leetcode0031 下一个排列-medium

1 题目&#xff1a; 下一个排列 官方标定难度&#xff1a;中等 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如&#xff0c;arr [1,2,3] &#xff0c;以下这些都可以视作 arr 的排列&#xff1a;[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一…

Suno的对手Luno:AI音乐开发「上传参考音频 - 方式二:通过URL的方式」 —— 「Luno Api系列|AI音乐API」第12篇

导读 今天来看下Luno Api的上传参考音频 - 方式一&#xff1a;通过二进制流的方式。 参考文件&#xff0c;主要是用于在创作的过程中&#xff0c;希望AI参考这个音乐的曲风和声音来进行创作&#xff0c; 这一节看看如何直接使用url的方式进行实现。 申请和使用 「已经有API…

【开源+代码解读】Search-R1:基于强化学习的检索增强大语言模型框架3小时即可打造个人AI-search

大语言模型(LLMs)在处理复杂推理和实时信息检索时面临两大挑战:知识局限性(无法获取最新外部知识)和检索灵活性不足(传统方法依赖固定检索流程)。现有方法如检索增强生成(RAG)和工具调用(Tool-Use)存在以下问题: RAG:单轮检索导致上下文不足,无法适应多轮交互场景…