1035 插入与归并(测试点6)

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

solution

  • 类型判断:插入排序中已排序的部分有序,未排序的和原数组元素相同;否则为归并排序
  • 测试点6:对于归并排序的子序列长度,不能简单视为前k个有序则子序列长度就是k
    例如该测试用例的归并排序的子序列长度应该为2,而非4
8
2 1 3 8 5 2 4 6
1 2 3 8 2 5 4 6
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 110;
int pre[maxn], did[maxn];
int main(){int n, cnt = 0, flag = 0, p, t;scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d", pre + i);}for(int i = 0; i < n; i++){scanf("%d", did + i);}for(p = 0; p < n; p++){if(p == 0) t = did[p];if(did[p] < t) break;t = did[p];cnt++;}for(; p < n; p++){if(did[p] != pre[p]){flag = 1;break;}}if(flag){printf("Merge Sort\n");t = 1;while(t){t = 0;for(int i = 0; i < n / cnt; i++){for(int j = i * cnt; j < (i + 1) * cnt - 1; j++){if(did[j] > did[j + 1]) t = 1;}}if(t) cnt /= 2;}cnt *= 2;for(int i = 0; i < n / cnt; i++){sort(did + i * cnt, did + (i + 1) * cnt);}sort(did + n / cnt * cnt, did + n);}else{printf("Insertion Sort\n");sort(did, did + cnt + 1);}for(int i = 0; i < n; i++){if(i) printf(" ");printf("%d", did[i]);}return 0;
} 

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

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

相关文章

2024海南省大数据教师培训-Hadoop集群部署

前言 本文将详细介绍Hadoop分布式计算框架的来源&#xff0c;架构和应用场景&#xff0c;并附上最详细的集群搭建教程&#xff0c;能更好的帮助各位老师和同学们迅速了解和部署Hadoop框架来进行生产力和学习方面的应用。 一、Hadoop介绍 Hadoop是一个开源的分布式计算框架&…

牛客java基础(一)

A 解析 : java源程序只允许一个public类存在 &#xff0c;且与文件名同名 ; D hashCode方法本质就是一个哈希函数&#xff0c;这是Object类的作者说明的。Object类的作者在注释的最后一段的括号中写道&#xff1a;将对象的地址值映射为integer类型的哈希值。但hashCode()并不…

SQL Chat:从SQL到SPEAKL的数据库操作新纪元

引言 SQL Chat是一款创新的、对话式的SQL客户端工具。 它采用自然语言处理技术&#xff0c;让你能够像与人交流一样&#xff0c;通过日常对话的形式对数据库执行查询、修改、创建及删除操作 极大地简化了数据库管理流程&#xff0c;提升了数据交互的直观性和效率。 在这个框…

【虚拟现实】一、AR与VR的基本原理

人不走空 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌赋&#xff1a;斯是陋室&#xff0c;惟吾德馨 增强现实&#xff08;AR&#xff09;和虚拟现实&#xff08;VR&#xff09;技术已经从科幻小说走入现实&#xf…

UltraScale+系列模块化仪器,可以同时用作控制器、算法加速器和高速数字信号处理器

基于 XCZU7EG / XCZU4EG / XCZU2EG • 灵活的模块组合 • 易于嵌入的紧凑型外观结构 • 高性能的 ARM Cortex 处理器 • 成熟的 FPGA 可编程逻辑 &#xff0c;基于 IP 核的软件库 基于 Xilinx Zynq UltraScaleMPSoC 的 FPGA 技术&#xff0c;采用 Xilinx Zynq UltraScale&a…

Spring-Security(二)OAuth2认证详解(持续更新)

Spring Security & Oauth2系列&#xff1a; Spring Security&#xff08;一&#xff09; 源码分析及认证流程 Spring Security&#xff08;二&#xff09;OAuth2认证详解及自定义异常处理 文章目录 1、OAuth2.0 简介1.1 OAuth2.0 相关名词解释1.2 四种授权模式 1.3 、OAu…

接口(API)开发,测试工具-apifox

前言 为什么需要接口&#xff08;API&#xff09;? 因为不同的平台或系统可能使用不同的技术栈、编程语言或数据格式。API提供了一个标准化的方式&#xff0c;使得这些不同的系统可以相互交换数据和功能调用&#xff0c;实现互操作性 在开发日常的项目交互中&#xff0c;不…

内网穿透的方式有哪些——快解析的优势

外网穿透内网技术&#xff0c;即内网映射&#xff0c;是把目标本地内网地址和端口发布到互联网&#xff0c;是一种由内网开放到外网的权限操作。那么&#xff0c;内网穿透的方法有哪些呢&#xff1f;做映射外网的方法。需要结合自己本地网络环境和应用场景来实施。这里分享三种…

Python Excel 指定内容修改

需求描述 在处理Excel 自动化时,财务部门经常有一个繁琐的场景,需要读取分发的Excel文件内容复制到汇总Excel文件对应的单元格内,如下图所示: 这种需求可以延申为,财务同事制作一个模板,将模板发送给各员工,财务同事需收取邮件将员工填写的excel文件下载到本机,再类似…

[FreeRTOS 基础知识] 任务调度 与 链表

文章目录 任务并行的概念RTOS如何实现多任务调度&#xff1f; 任务并行的概念 在生活中&#xff0c;经常出现一心多用的情况。比如你需要一边吃饭一边手机回复信息&#xff0c;这里面就存在两个任务&#xff1a;任务一、吃饭。任务二、手机回复信息。 假如你无法一心多用&…

FreeRTOS实时系统 在任务中增加数组等相关操作 导致单片机起不来或者挂掉

在调试串口任务中增加如下代码&#xff0c;发现可以用keil进行仿真&#xff0c;但是烧录程序后&#xff0c;调试串口没有打印&#xff0c;状态灯也不闪烁&#xff0c;单片机完全起不来 博主就纳了闷了&#xff0c;究竟是什么原因&#xff0c;这段代码可是公司永流传的老代码了&…

平面设计神器CorelDRAW2021精简版,你值得拥有!

亲爱的设计师小伙伴们&#xff0c;今天我要为大家种草一款神奇的软件——CorelDRAW平面设计软件2021精简版&#xff01;&#x1f929;✨作为一名专业的图形设计师&#xff0c;我深知一个好工具对于我们的工作有多么重要。而这款软件简直就是我们设计师的救星&#xff01;&#…

【MySQL数据库】:MySQL索引特性

目录 索引的概念 磁盘 磁盘的基本特征 MySQL与磁盘交互的基本单位 索引的理解 建立测试表 理解单个Page 理解多个Page 页目录 单页情况 多页情况 索引的数据结构 聚簇索引 VS 非聚簇索引 索引操作 创建主键索引 创建唯一索引 创建普通索引 创建全文索引 查询…

每日一题——Python实现PAT乙级1099 性感素数(举一反三+思想解读+逐步优化)

一个认为一切根源都是“自己不够强”的INTJ 个人主页&#xff1a;用哲学编程-CSDN博客专栏&#xff1a;每日一题——举一反三Python编程学习Python内置函数 Python-3.12.0文档解读 目录 我的写法 专业点评 时间复杂度分析 空间复杂度分析 综合点评 我要更强 优化点 …

力扣每日一题130:被围绕的区域

题目 中等 相关标签 相关企业 给你一个 m x n 的矩阵 board &#xff0c;由若干字符 X 和 O &#xff0c;找到所有被 X 围绕的区域&#xff0c;并将这些区域里所有的 O 用 X 填充。 示例 1&#xff1a; 输入&#xff1a;board [["X","X","X"…

U盘文件系统结构损坏的应对与预防

在数字化时代&#xff0c;U盘作为便携式存储设备&#xff0c;其重要性不言而喻。然而&#xff0c;当U盘文件系统结构损坏时&#xff0c;我们可能会面临数据丢失的风险。本文将深入探讨U盘文件系统结构损坏的问题&#xff0c;分析其产生的原因&#xff0c;并给出相应的数据恢复方…

基于pytoch卷积神经网络水质图像分类实战

具体怎么学习pytorch&#xff0c;看b站刘二大人的视频。 完整代码&#xff1a; import numpy as np import os from PIL import Image import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data…

时序数据库是Niche Market吗?

引言 DB-Engines的流行程度排行从其评估标准[4]可以看出完全不能够做为市场规模的评估标准。甚至于在知道市场规模后可以用这个排行作为一个避雷手册。毕竟现存市场小&#xff0c;可预见增长规模小&#xff0c;竞争大&#xff0c;创新不足&#xff0c;那只能卷价格&#xff0c…

【文献阅读】LORA: LOW-RANK ADAPTATION OF LARGE LANGUAGE MODELS

目录 1. motivation2. overall3. model3.1 low rank parametrized update matrices3.2 applying lora to transformer 4. limitation5. experiment6. 代码7. 补充参考文献 1. motivation 常规的adaptation需要的微调成本过大现有方法的不足&#xff1a; Adapter Layers Introd…

.net core 使用js,.net core 使用javascript,在.net core项目中怎么使用javascript

.net core 使用js&#xff0c;.net core 使用javascript&#xff0c;在.net core项目中怎么使用javascript 我项目里需要用到“文字编码”&#xff0c;为了保证前端和后端的编码解码不处bug, 所以&#xff0c;我在项目中用了这个 下面推荐之前在.net F4.0时的方法 文章一&#…