构造+模拟,CF1148C. Crazy Diamond

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 1148C - Codeforces


二、解题报告

1、思路分析

题目提示O(5n)的解法了,事实上我们O(3n)就能解决,关键在于1,n的处理

我们读入数据a[],代表初始数组,p[i]代表 i 的下标

如果p[i] != i

说明需要交换

a[p[i]] 一定能跟a[1]或者a[n]交换, a[i]也一定能跟1或n交换

假设 a[i]  的可交换位置为x,a[p[i]] 的可交换位置为y(x、y只可能为1、n)

那么我们使得元素i从p[i] -> y -> x -> i 就在3步之内让i到达了下标i

此时a[1] 和 a[n]可能不满足a[1] = 1, a[n] = n

事实上我们将每个元素调整完后再调整1和n即可

这也是为什么能从O(5n)优化到O(3n)

 

2、复杂度

时间复杂度: O(3n)空间复杂度:O(n)

3、代码详解

#include <bits/stdc++.h>
using PII = std::pair<int, int>;
const int N = 3e5 + 10;
int p[N], a[N], n, s;
std::vector<PII> path;void swap(int x, int y) {std::swap(p[a[x]], p[a[y]]);std::swap(a[x], a[y]);path.emplace_back(x, y);
}int main () {std::cin >> n;path.reserve(5 * n);for (int i = 1; i <= n; i ++ ) std::cin >> a[i], p[a[i]] = i;for (int i = 1; i <= n / 2; i ++ ) {if (p[i] != i) {if (p[i] <= n / 2) {swap(p[i], n);swap(i, n);}else {swap(1, p[i]);swap(1, n);swap(i, n);}}}for (int i = n / 2 + 1; i <= n; i ++ ) {if (p[i] != i) {if (p[i] > n / 2) {swap(1, p[i]);swap(1, i);}else {swap(p[i], n);swap(1, n);swap(1, i);}}}if (a[1] != 1) swap(1, n);std::cout << path.size() << '\n';for (auto [x, y] : path) std::cout << x << " " << y << '\n';return 0;
}

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

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

相关文章

PYQT5点击Button执行多次问题解决方案(亲测)

PYQT5点击Button却执行多次问题 使用pyqt5时遇到问题&#xff0c;UI上按钮点击一次&#xff0c;对应的槽函数却执行了3遍 首先&#xff0c;确认函数名无冲突&#xff0c;UI button名无命名冲突&#xff0c;下图是简单的示例程序&#xff1a; 运行后&#xff0c;点击按钮&#…

vs工程添加自定义宏

一、简介 用户可以添加自定义宏变量方便工程路径名称的修改和配置 例&#xff1a;$(SolutionDir) 为解决方案路径&#xff0c;$(PojectDir) 为工程所在路径 测试环境&#xff1a;vs2017&#xff0c;qt5.14.0 二、配置 1、打开属性窗口&#xff1a;视图-》其他窗口-》属性管…

C语言-----指针数组 \ 数组指针

一 指针数组 用来存放指针的数组 int arr[10]; //整型数组 char ch[5]; //字符数组 int * arr[6]; //存放整型指针的数组 char * arr[5]; //存放字符指针的数组 // 指针数组的应用 int main() {int arr1[] { 1,2,3,4,5 };int arr2[] { 2,3,4,5,6 };int arr3[] { 3,4,…

05-28 周二 TTFT, ITL, TGS 计算过程以及LLama2推理代码调试过程

05-28 周二 LLama2推理代码调试过程 时间版本修改人描述2024年5月28日15:03:49V0.1宋全恒新建文档 简介 本文主要用于求解大模型推理过程中的几个指标&#xff1a; 主要是TTFT&#xff0c;ITL&#xff0c; TGS 代码片段 import osdata_dir "/workspace/models/" m…

元宇宙对于品牌营销有哪些影响?品牌如何加入?

元宇宙对于品牌营销带来了许多新的营销方式和策略&#xff0c;这些方式在传统营销中是无法实现的。以下是元宇宙对于品牌营销的主要营销方式&#xff1a; 1、虚拟展示&#xff1a; 利用元宇宙技术&#xff0c;品牌可以将产品或服务在虚拟世界中进行展示&#xff0c;用户可以通…

Slurm集群使用基础

Introduction 我们在做生物信息分析时&#xff0c;对于大规模的上游数据的处理&#xff0c;一般需要在大型服务器或集群上进行。我最早接触并使用的是一个基于SLURM调度系统的集群&#xff0c;在此记录一下基础使用方法。 高性能计算集群&#xff08;High-Performance Comput…

贪心(临项交换)+01背包,蓝桥云课 搬砖

一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 0搬砖 - 蓝桥云课 (lanqiao.cn) 二、解题报告 1、思路分析 将物品按照w[i] v[i]升序排序然后跑01背包就是答案 下面证明&#xff1a;&#xff08;不要问怎么想到的&#xff0c;做题多了就能想到&#xff…

氢燃料电池汽车行业发展

文章目录 前言 市场分布 整车销售 发动机配套 氢气供应 发展动能 参考文献 前言 见《氢燃料电池技术综述》 见《燃料电池工作原理详解》 见《燃料电池发电系统详解》 见《燃料电池电动汽车详解》 市场分布 纵观全球的燃料电池汽车市场&#xff0c;截至2022年底&#xff…

Git——pull request详细教程

当我们需要协助其他仓库完成更改时&#xff0c;往往会用到git中的Pull Request操作&#xff0c;从而方便团队的协作管理和代码持续集成。 下面是详细的教程步骤。 一. Fork目标项目 比如说我现在要fork以下Qwen-VL的项目&#xff0c;如图所示&#xff1a; 随后点击Create即可…

转行一年了

关注、星标公众号&#xff0c;直达精彩内容 ID&#xff1a;技术让梦想更伟大 整理&#xff1a;李肖遥 来公司一年了。 说是转行其实还是在半导体行业&#xff0c;熟悉我的朋友知道 &#xff0c;我在18年开始进入半导体行业&#xff0c;那个时候想着行业很重要&#xff0c;站对了…

【全开源】场馆预定系统源码(ThinkPHP+FastAdmin+UniApp)

一款基于ThinkPHPFastAdminUniApp开发的多场馆场地预定小程序&#xff0c;提供运动场馆运营解决方案&#xff0c;适用于体育馆、羽毛球馆、兵乒球馆、篮球馆、网球馆等场馆。 场馆预定系统源码&#xff1a;打造高效便捷的预定体验 一、引言&#xff1a;数字化预定时代的来临 …

新火种AI|寻求合作伙伴,展开豪赌,推出神秘AI项目...苹果能否突破AI困境?

作者&#xff1a;小岩 编辑&#xff1a;彩云 2024年&#xff0c;伴随着AI技术的多次爆火&#xff0c;不仅各大科技巨头纷纷进入AI赛道展开角力&#xff0c;诸多智能手机厂商也纷纷加紧布局相关技术&#xff0c;推出众多AI手机。作为手机领域的龙头老大&#xff0c;苹果自然是…

LeetCode---链表

203. 移除链表元素 给你一个链表的头节点 head 和一个整数 val &#xff0c;请你删除链表中所有满足 Node.val val 的节点&#xff0c;并返回 新的头节点 。 代码示例1&#xff1a;(直接使用原来的链表来进行移除节点操作) //时间复杂度: O(n) //空间复杂度: O(1) class Solu…

啊哈!算法-第2章-栈、队列、链表

啊哈!算法-第2章-栈、队列、链表 第1节 解密qq号——队列第2节 解密回文——栈第3节 纸牌游戏——小猫钓鱼第4节 链表第5节 模拟链表 第1节 解密qq号——队列 新学期开始了&#xff0c;小哈是小哼的新同桌(小哈是个大帅哥哦~)&#xff0c;小哼向小哈询问 QQ 号&#xff0c; 小…

有限元之抛物型方程初边值问题解法

目录 一、原方程的变分形式 二、有限元法进行空间半离散 三、差分法进行时间全离散 四、相关量的数值计算 五、编程时的说明 六、算例实现 6.1 C代码 6.2 计算结果 本节我们将采用有限元法联合差分法来数值求解抛物型方程的初边值问题&#xff1a; 其中常数。 一、原方…

Element-UI 入门指南:从安装到自定义主题的详细教程

Element-UI 是一个基于 Vue.js 的前端组件库&#xff0c;它提供了丰富的 UI 组件&#xff0c;可以帮助开发者快速构建高质量的用户界面。以下是使用 Element-UI 的快速入门指南&#xff1a; 安装 Element-UI Element-UI 是一个基于 Vue.js 的组件库&#xff0c;它提供了丰富的…

LangChain入门开发教程(一):Model I/O

官方文档&#xff1a;https://python.langchain.com/docs/get_started/introduction/ LangChain是一个能够利用大语言模型&#xff08;LLM&#xff0c;Large Language Model&#xff09;能力进行快速应用开发的框架&#xff1a; 高度抽象的组件&#xff0c;可以像搭积木一样&a…

LeetCode2336无限集中的最小数字

题目描述 现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, …] 。实现 SmallestInfiniteSet 类&#xff1a;SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。int popSmallest() 移除 并返回该无限集中的最小整数。void addBack(int num) 如果正整数 …

基于Python实现 HR 分析(逻辑回归和基于树的机器学习)【500010104】

介绍 数据集说明 此数据集包含与员工有关的综合属性集合&#xff0c;从人口统计细节到与工作相关的因素。该分析的主要目的是预测员工流动率并辨别导致员工流失的潜在因素。 在这个数据集中&#xff0c;有14,999行&#xff0c;10列&#xff0c;以及这些变量&#xff1a;满意度…

Python轻量级的插件框架库之pluginbase使用详解

概要 在软件开发中,插件系统是一个常见的需求。插件系统允许开发者动态加载和卸载功能模块,从而提高应用程序的灵活性和可扩展性。Python的pluginbase库是一个轻量级的插件框架,旨在简化插件系统的构建过程。pluginbase库提供了一套简单易用的API,使开发者能够快速集成插件…