曲师大2023大一新生排位赛-B.Sort题解

题目描述

插入排序是一种非常常见且简单的排序算法。王同学是一名大一的新生,今天许师哥刚刚在上课的时候讲了插入排序算法。

假设比较两个元素的时间为 O\left ( 1 \right ),则插入排序可以以 O\left ( n^2 \right ) 的时间复杂度完成长度为 n� 的数组的排序。不妨假设这 n 个数字分别存储在a_1,a_2,......,a_n​ 之中,则如下伪代码给出了插入排序算法的一种最简单的实现方式:
下面是插入排序的示范代码:


for (int i = 1; i <= n; i++)
      for (int j = i; j >= 2; j--)
            if (a[j] < a[j-1]) {
		  int t = a[j-1];
		  a[j-1] = a[j];
		  a[j] = t;
	    }


为了帮助王同学更好的理解插入排序,许师哥给他留下了这么一道课后作业:

许师哥给了一个长度为 n 的数组 a,数组下标从 1 开始,并且数组中的所有元素均为非负整数。王同学需要支持在数组 a 上的 Q 次操作,操作共两种,参数分别如下:
1 x v:这是第一种操作,会将 a 的第 x 个元素,也就是 a_x​ 的值,修改为 v。保证 1 \leq x \leq n, 1 \leq v \leq 10 ^9注意这种操作会改变数组的元素,修改得到的数组会被保留,也会影响后续的操作
 

2 x:这是第二种操作,假设许师哥按照上面的伪代码对 a 数组进行排序,你需要告诉许师哥原来 a 的第 x 个元素,也就是 a_x​,在排序后的新数组所处的位置。保证 1 \leq x \leq n注意这种操作不会改变数组的元素,排序后的数组不会被保留,也不会影响后续的操作

许师哥不喜欢过多的修改,所以他保证类型 11 的操作次数不超过 50005000。

输入描述

第一行,包含两个正整数 n,Q\left ( 1 \leq n \leq 8000,1 \leq Q \leq 2 \times 10^5 \right ),表示数组长度和操作次数。
第二行,包含 n 个空格分隔的非负整数,其中第 i 个非负整数表示 a_i \left ( 1 \leq a _i \leq 10^9 \right )
接下来 Q 行,每行 2∼3个正整数,表示一次操作,操作格式见【题目描述】
输入数据保证 1 \leq x \leq n, 1 \leq v \leq 10 ^9,同时,在所有 Q 次操作中,至多有 5000 次操作属于类型一。

输出描述

对于每一次类型为 2 的询问,输出一行一个正整数表示答案。

样例

输入:

3 4
3 2 1
2 3
1 3 2
2 2
2 3

输出:

1
1
2

输入:

10 10
877332633 234569527 229171089 600324455 1458624 887548760 574229391 234569527 202374341 849045846
2 7
1 2 234569527
1 4 600324455
2 6
2 9
2 6
2 3
1 5 246345024
1 6 856960762
2 7

输出:

6
10
2
10
3
6

思路:

题目告诉我们至多5000次修改,很明显修改次数少,查询次数多。所以我们不能在查询时间进行排序操作的修改,但是可以在修改时间进行操作。
我们可以先对数据进行排序,原结构体数组记录排好序的下表,将排序结构体中对应好原数组的位置。
修改时间操作的理论:我将原来的数和修改后的数之间的下表进行修改,大于和小于这两个数的下表不需要修改,因为重新排序也不影响这两个数之外的位置,所以只需要修改原数和修改数区间内的下表即可。这样就可以可使用O(n)的时间复杂度完成这一操作
查询时间的理论:在修改时间同时维护这这两个结构体数组之间的对应关系,所以查询的时间复杂度是O(1)

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 8100;
struct node1
{
    int value,pxb;
}a[N];//原数组,对应的是该位置的值,该位置排序后的下标
struct node2
{
    int vlaue,yxb;
}b[N];//排序数组,对应的是该位置的值,该位置在原数组中对应的下标
bool cmp(node2 x,node2 y){
    if(x.vlaue == y.vlaue)
        return x.yxb < y.yxb;
    return x.vlaue < y.vlaue;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);
    int n,q;
    cin >> n >> q;
    for(int i = 1;i <= n;i++){
        int x;
        cin >> x;
        b[i].vlaue = x;
        b[i].yxb = i;
    }
    sort(b+1,b+1+n,cmp);
    // for(int i = 1;i <= n;i++){
    //     cout << b[i].vlaue << endl;
    // }
    for(int i = 1;i <= n;i++){
        a[b[i].yxb].value = b[i].vlaue;
        a[b[i].yxb].pxb = i;
    }
    // for(int i = 1;i <= n;i++){
    //     cout << a[i].pxb << " " << a[i].value << endl;
    // }
    while(q--){
        int op;
        cin >> op;
        if(op == 1){
            int x,v;
            cin >> x >> v;
            int yu = a[x].value;
            int xi = v;
            a[x].value = v;
            b[a[x].pxb].vlaue = v;
            int i = a[x].pxb;
            //两个循环只会进入一个
            //这个循环时说修改后的值比原来的值小了,用排序的数组往前找他自己的位置
            while(i != 1 &&( b[i].vlaue < b[i - 1].vlaue || (b[i].vlaue == b[i - 1].vlaue && b[i].yxb < b[i-1].yxb))){
                swap(b[i],b[i - 1]);
                a[b[i].yxb].pxb=i;
                a[b[i].yxb].value=b[i].vlaue;
                a[b[i - 1].yxb].pxb=i - 1;
                a[b[i - 1].yxb].value=b[i - 1].vlaue;
                i--;
            }
            //这个循环,修改后的值比原来的值大了,用排序数组往后找他自己的位置
            while(i != n &&( b[i].vlaue > b[i + 1].vlaue || (b[i].vlaue == b[i + 1].vlaue && b[i].yxb > b[i+1].yxb))){
                swap(b[i],b[i + 1]);//交换之后需要维护原来的对应关系
                a[b[i].yxb].pxb=i;
                a[b[i].yxb].value=b[i].vlaue;
                a[b[i + 1].yxb].pxb=i + 1;
                a[b[i + 1].yxb].value=b[i + 1].vlaue;
                i++;
            }
        }
        if(op == 2){
            int x;
            cin >> x;
            cout << a[x].pxb << "\n";
        }
    }
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

JavaWeb(4)——HTML、CSS、JS 快速入门

一、JavaScript 数组 数组筛选&#xff08;查找&#xff0c;将原来数组中的某些数据去除&#xff09; <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content&quo…

【Hydro】一个简单的HBV水文模型产流Python实现

说明 HBV模型包括一系列自由参数&#xff0c;其值可以通过率定得到。同时也包括一些描述流域和气候特征的参数&#xff0c;它们的值在模型率定是假定不变。子流域的划分使得在一个子流域中可能有很多参数值。虽然在大多数应用中&#xff0c;各子流域之间参数值只有很小的变化&a…

webpack插件compression-webpack-plugin

Vue配置compression-webpack-plugin实现Gzip压缩 1、为什么要压缩&#xff1f; 打包的时候开启gzip可以很大程度减少包的大小&#xff0c;页面大小可以变为原来的30%甚至更小&#xff0c;非常适合于上线部署。更小的体积对于用户体验来说就意味着更快的加载速度以及更好的用户…

使用IDEA社区版创建SpringBoot项目

文章目录 1.关于IDEA社区版的版本2.下载Spring Boot Helper3.创建项目4.配置Maven国内源4.1找不到settings.xml的情况4.2找得到settings.xml的情况 4.3删除repository目录下的所有文件和目录5.加载项目6.解决org.springframework.boot:spring-boot-starter-parent:pom:2.7.13.R…

NXP i.MX 6ULL工业开发板硬件说明书( ARM Cortex-A7,主频792MHz)

前 言 本文档主要介绍TLIMX6U-EVM评估板硬件接口资源以及设计注意事项等内容。 创龙科技TLIMX6U-EVM是一款基于NXP i.MX 6ULL的ARM Cortex-A7高性能低功耗处理器设计的评估板&#xff0c;由核心板和评估底板组成。核心板经过专业的PCB Layout和高低温测试验证&#xff0c;稳…

我们如何在 Elasticsearch 8.6、8.7 和 8.8 中加速数据摄入

作者&#xff1a;Adrien Grand, Joe Gallo, Tyler Perkins 正如你们中的一些人已经注意到的&#xff0c;Elasticsearch 8.6、8.7 和 8.8 在各种数据集上带来了良好的索引加速&#xff0c;从简单的关键字到繁重的 KNN 向量&#xff0c;以及摄取管道繁重的摄取工作负载。 摄取涉及…

Java Mybatis拓展03

0目录 1.MyBatis当实体类和数据库字段名不对应 2.多表查询 1.MyBatis当实体类和数据库字段名不对应 方法2 测试 多表查询 加入子标签association 模糊查询 加入Address 对象 三表联查 2.五表联查 测试

使用 appium 进行微信小程序的自动化测试

目录 前言&#xff1a; 微信小程序结构 自动化用例的调整 示例代码 后记 前言&#xff1a; 微信小程序是一种流行的移动应用程序&#xff0c;它在移动设备上提供了丰富的功能和用户体验。为了确保微信小程序的质量和稳定性&#xff0c;自动化测试是必不可少的一环。Appiu…

el-table找出当前单元格与对应的上下列的值

当前单元格与对应的上下列的值如果不相同就设置个红色边框 当前单元格与对应的上下列的值如果不相同就设置个红色边框 当前单元格与对应的上下列的值如果不相同就设置个红色边框 以下是示例代码&#xff0c;对tableData数据的name字段进行处理 如果当前name值与上一条数据的na…

港联证券-尾盘集合竞价拉升意味着什么意思?

在股票市场中&#xff0c;尾盘集合竞价是指每个交易日的最后几分钟&#xff0c;即下午14:57到3:00之间的交易。在这段时间内&#xff0c;所有股票的买卖都将以竞价的方式进行&#xff0c;最终价格以最高买价与最低卖价的平均值确定&#xff0c;成交量也将作为当日的收盘价和成交…

科普一下Elasticsearch中BM25算法的使用

首先还是先了解几个概念&#xff0c;Elasticsearch是一个开源的分布式搜索和分析引擎&#xff0c;它使用一系列算法来计算文档的相关性分数&#xff08;relevance score&#xff09;。这些算法用于确定查询与文档的匹配程度&#xff0c;以便按相关性对搜索结果进行排序。以下是…

Unity URP 2D光照导入与配置

上面随时间变化的火烧云和晚霞&#xff0c;篝火的呼吸光照&#xff0c;都是URP的功劳。 1.什么是URP&#xff1f; URP 全称为 Universal Render Pipeline(通用渲染管线)。 它的特点是在手游和端游均能在保持性能的同时有良好的效果 也就说在多数情况下&#xff0c;在下面的平台…

10亿级用户,如何做 熔断降级架构?微信和hystrix的架构对比

说在前面 在40岁老架构师 尼恩的读者社区(50)中&#xff0c;最近有小伙伴拿到了一线互联网企业如极兔、有赞、希音、百度、网易、滴滴的面试资格&#xff0c;遇到一几个很重要的面试题&#xff1a; (1) 什么是熔断&#xff0c;降级&#xff1f;如何实现&#xff1f; (2) 服务熔…

linux内核调试工具记录

Linux性能测试使用的工具在github网站可见&#xff0c;网址如下&#xff1a; slides: http://www.slideshare.net/brendangregg/linux-performance-analysis-new-tools-and-old-secrets video: https://www.usenix.org/conference/lisa14/conference-program/presentation/greg…

LLM微调 | LoRA: Low-Rank Adaptation of Large Language Models

&#x1f525; 发表于论文&#xff1a;(2021) LoRA: Low-Rank Adaptation of Large Language Models &#x1f604; 目的&#xff1a;大模型预训练微调范式&#xff0c;微调成本高。LoRA只微调新增的小部分参数。 文章目录 1、背景2、动机3、LoRA原理4、总结 1、背景 adapter…

BUFG/BUFGCE/BUFH/BUFHCE/BUFH/BUFGHCE/BUFMR/BUFMRCE/BUFR/IBUF/IBUFDS

本文对BUFG/BUFGCE/BUFH/BUFHCE简单介绍&#xff0c;便于后续查看。 原语的使用&#xff1a;在vivado中找到所要用的原语&#xff0c;直接将其实例化到设计中即可。 文章目录 BUFGBUFGCEBUFHBUFHCEBUFMRBUFRBUFMRCEIBUFIBUFDS 下图为 7 系列 FPGA 时钟架构图&#xff1a; BU…

又卡了,大数据平台容器化运维走起

文章目录 一、背景二、方案总结三、方案实施3.0 转移数据修改docker默认存储位置3.1 手动清理3.2 定时容器日志清理3.3 限制 Docker 容器日志大小 大家好&#xff0c;我是脚丫先生 (o^^o) 大数据基础平台的搭建&#xff0c;我采用的是全容器化Apache的大数据组件。 之前还很美…

Java对象深拷贝、浅拷贝之枚举类型

问题&#xff1a;为什么属于引用类型的enum不会有深拷贝浅拷贝的问题&#xff1f; 解释&#xff1a; 在Java中&#xff0c;枚举类型是一种特殊的类类型。每个枚举值都是该枚举类型的一个实例&#xff0c;并且这些实例在枚举类型被初始化时就已经被创建。这些实例在程序的整个…

如何二次封装一个el-table组件并二次复用

*注:示例使用的是vue3和element进行二次封装的 首先我们来看效果图&#xff08;总共可以分为以下几个模块&#xff09;&#xff1a; 表格数据操作按钮区域表格信息提示区域表格主体内容展示区域表格分页区域 表单搜索没有封装在这里是为了降低代码的耦合性(有兴趣的可以查看我…

rt-thread构建含c++源码的工程

RT-Thread Components > C/C and POSIX layerscons构建项目会出错&#xff1a; vim libraries/SConscript &#xff0c;删除 pico-sdk/src/rp2_common/pico_standard_link/new_delete.cpp&#xff08;切记不要注释&#xff0c;要删除&#xff09; 再次scons构建项目&#…