当前位置: 首页 > news >正文

洛谷: P7910 [CSP-J 2021] 插入排序

题目链接:P7910 [CSP-J 2021] 插入排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:

1.定义结构体,将输入数据和它是第几位绑定起来。增加一个数组f[x],记录原来序列中的第x个在新序列中的位置,每执行一次修改操作,我们需要对数组重新排序一次,意味着f[x]要更新一次。

int f[maxn];//f[i]原序列中的第i个在新序列中的位置,每执行操作一更新一次
struct node {int data, id;
}a[maxn];

2.操作二的查询即是将f[x]输出出来。

int x;
cin >> x;
cout << f[x] << endl;

3.每次操作一执行完成数组重新排序一次。两个for循环的原因,这个位置上的数字可能变大可能变小。如果变大需要将其往后冒泡找到他应该在的位置。反之,往前冒泡(我看题解没写这个判断条件,对于本菜鸟很容易造成误导,这里加上了)。

			int x, y;cin >> x >> y;//设置ax=yint tmp = a[f[x]].data;a[f[x]].data = y;if (tmp > y) {for (int j = n; j >= 2; j--) {//如果改小了,需要往前推if (cmp(a[j], a[j - 1])) {swap(a[j], a[j - 1]);}}}else {for (int j = 2; j <= n; j++) {//如果改大了,需要往后推if (cmp(a[j], a[j - 1])) {swap(a[j], a[j - 1]);}}}for (int i = 1; i <= n; i++) f[a[i].id] = i;

完整代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int f[maxn];//f[i]原序列中的第i个在新序列中的位置,每执行操作一更新一次
struct node {int data, id;
}a[maxn];
bool cmp(node n1,node n2) {if (n1.data != n2.data) return n1.data < n2.data;return n1.id < n2.id;//稳定排序
}
int main() {int n, Q;cin >> n >> Q;for (int i = 1; i <= n; i++) {cin >> a[i].data;a[i].id = i;}sort(a + 1, a + 1 + n, cmp);//为了操作2做准备for (int i = 1; i <= n; i++) f[a[i].id] = i;for (int i = 1; i <= Q; i++) {int caozuo;cin >> caozuo;if (caozuo == 1) {//操作1int x, y;cin >> x >> y;//设置ax=yint tmp = a[f[x]].data;a[f[x]].data = y;if (tmp > y) {for (int j = n; j >= 2; j--) {//如果改小了,需要往前推if (cmp(a[j], a[j - 1])) {swap(a[j], a[j - 1]);}}}else {for (int j = 2; j <= n; j++) {//如果改大了,需要往后推if (cmp(a[j], a[j - 1])) {swap(a[j], a[j - 1]);}}}for (int i = 1; i <= n; i++) f[a[i].id] = i;}else {int x;cin >> x;cout << f[x] << endl;}}return 0;
}

---- Last Blog  ----

相关文章:

洛谷: P7910 [CSP-J 2021] 插入排序

题目链接:P7910 [CSP-J 2021] 插入排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路: 1.定义结构体&#xff0c;将输入数据和它是第几位绑定起来。增加一个数组f[x]&#xff0c;记录原来序列中的第x个在新序列中的位置&#xff0c;每执行一次修改操作&#xff0c;我们…...

Lua weak表

之前写过一篇博客专门介绍了weak表&#xff1a;Lua弱引用表-CSDN博客&#xff0c;这两天阅读了《programming in lua》后有了些新的体会&#xff0c;在这里只做一些之前没有了解的补充内容。 定义 Lua 自动进行内存的管理。程序只能创建对象&#xff08;表&#xff0c;函数等…...

DS:二叉树的顺序结构及堆的实现

创作不易&#xff0c;兄弟们给个三连&#xff01;&#xff01; 一、二叉树的顺序存储 顺序结构指的是利用数组来存储&#xff0c;一般只适用于表示完全二叉树&#xff0c;原因如上图&#xff0c;存储不完全二叉树会造成空间上的浪费&#xff0c;有的人又会问&#xff0c;为什么…...

python从入门到精通(十九):python的多线程详细使用

python的多线程详细使用 1.什么是线程2.线程的作用3.导入线程4.创建线程启动线程线程阻塞线程的方法守护线程线程阻塞2个都是守护线程1个是守护线程线程间通信1.什么是线程 线程是操作系统能够进行运算调度的最小单位。它被包含在进程之中,是进程中的实际运作单位。一条线程指…...

【More Effective C++】条款19:了解临时对象的来源

临时对象&#xff1a;没有命名&#xff0c;不会出现在源代码中 帮助隐式类型转换成功而创建的对象 编译器创建一个类型为string的临时对象&#xff0c;以buffer作为参数&#xff0c;调用string的构造函数&#xff1b;str绑定到了这个临时对象上函数返回时&#xff0c;这个临时…...

站在C/C++的肩膀速通Java面向对象

默认学过C或C&#xff0c;对变量、表达式、选择、循环都会。 运行特征 解释型语言&#xff08;JavaScript、Python等&#xff09; 源文件-(平台专属解释器)->解释器中执行编译型语言&#xff08;C、Go等&#xff09; 源文件-(平台编译器)->平台可执行文件Java 源文件-(…...

【AI视野·今日Robot 机器人论文速览 第七十八期】Wed, 17 Jan 2024

AI视野今日CS.Robotics 机器人学论文速览 Wed, 17 Jan 2024 Totally 49 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Robotics Papers Safe Mission-Level Path Planning for Exploration of Lunar Shadowed Regions by a Solar-Powered Rover Authors Olivier L…...

flask cors 跨域问题解决

座右铭&#xff1a;怎么简单怎么来&#xff0c;以实现功能为主。 欢迎大家关注公众号与我交流 环境安装 pip install -U flask-cors 示例代码 from flask import Flask from flask_cors import CORS, cross_originapp Flask(__name__) CORS(app, supports_credentialsTrue)…...

18 19 SPI接口的74HC595驱动数码管实验

1. 串行移位寄存器原理&#xff08;以四个移位寄存器为例&#xff09; 1. 通过移位寄存器实现串转并&#xff1a;一个数据输入端口可得到四位并行数据。 通过给data输送0101数据&#xff0c;那么在经过四个时钟周期后&#xff0c;与data相连的四个寄存器的输出端口得到了0101…...

计算机网络概述习题拾遗

学习目标&#xff1a; 自下而上第一个提供端到端服务的层次 路由器、交换机、集线器实现的功能层 TCP/IP体系结构的网络接口层对应OSI体系结构的哪两个层次 分组数量对总时延的影响 如果这篇文章对您有帮助&#xff0c;麻烦点赞关注支持一下动力猿吧&#xff01; 学习内容…...

你的电脑关机吗

目录 程序员为什么不喜欢关电脑&#xff1f; 电脑长时间不关机会怎样? 电脑卡顿 中度风险 硬件损耗 能源浪费 散热问题 软件问题 网络安全问题 程序员为什么不喜欢关电脑&#xff1f; 大部分人都会选择将电脑进行关机操作。其实这不难理解&#xff0c;毕竟人类都需要…...

flask+python儿童福利院管理系统pycharm毕业设计项目

本系统解决了儿童福利院管理事务中的主要问题&#xff0c;包括首页、个人中心、爱心人士管理、员工管理、后勤人员管理、儿童信息管理、院所风采管理、活动管理、食谱管理、领养流程管理、政策法规管理、楼栋管理、宿舍管理、领养申请管理、义工申请管理、捐赠信息管理、宿舍物…...

React:高阶组件|ref转发

高阶组件 参考文档&#xff1a;高阶组件 – React (reactjs.org) 高阶组件&#xff08;Higher-Order Components&#xff0c;简称 HOC&#xff09;是React中用于复用组件逻辑的一种高级技巧。具体而言&#xff1a;高阶组件是参数为组件&#xff0c;返回值为新组件的函数。 组件…...

AI:127-基于卷积神经网络的交通拥堵预测

🚀点击这里跳转到本专栏,可查阅专栏顶置最新的指南宝典~ 🎉🎊🎉 你的技术旅程将在这里启航! 从基础到实践,深入学习。无论你是初学者还是经验丰富的老手,对于本专栏案例和项目实践都有参考学习意义。 ✨✨✨ 每一个案例都附带有在本地跑过的关键代码,详细讲解供…...

MongoDB聚合操作符:$abs

$abs聚合操作符用于返回数值的绝对值。 语法 { $abs: <数值> }<数值>表达式可以是任何能被解析为数值的合法表达式。 用法 如果$abs的<number>参数被解析为null值或引用不存在的字段&#xff0c;将返回null&#xff0c;如果参数被解析为NaN&#xff0c;也…...

【element-ui】输入框组件el-input输入数字/输出Number类型:type=“number“、v-model.number用法

输入框组件el-input输入数字/输出Number类型 1、基础用法 输入&#xff1a;任何文本 → 输出&#xff1a;String类型 <el-input v-model"inputText"></el-input> <!-- 输入 abc —— inputText输出 "abc" 输入 123 —— inputText输出 …...

算法与数据结构

算法与数据结构 前言 什么是算法和数据结构&#xff1f; 你可能会在一些教材上看到这句话&#xff1a; 程序 算法 数据结构 算法&#xff08;Algorithm&#xff09;&#xff1a;是指解题方案的准确而完整的描述&#xff0c;是一系列解决问题的清晰指令&#xff0c;算法代…...

C++动态规划-线性dp算法

莫愁千里路 自有到来风 CSDN 请求进入专栏 X 是否进入《C专栏》? 确定 目录 线性dp简介 斐波那契数列模型 第N个泰波那契数 思路&#xff1a; 代码测试&#xff1a; 三步问题 思路&#xff1a; 代码测试&#xff1a; 最小花费爬楼梯 思路…...

基于 Python 深度学习的电影评论情感分析系统,附源码

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12W、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…...

如何查看Apple Watch的步数?这里提供几个方法

所有Apple Watch都配有内置计步器,即具有步进跟踪功能。当你第一次设置手表时,你的Apple Watch将自动开始计算步数。让我们看看如何在Apple Watch上查看步数。​ 使用活动应用程序 1、按下Apple Watch上的数字皇冠,打开应用程序屏幕。 2、点击活动应用程序。 3、你会看到…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...