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

【CSP2019 模拟赛】Time

题目描述:

        小 A 现在有一个长度为 𝑛 的序列 {𝑥𝑖},但是小 A 认为这个序列不够优美。 小 A 认为一个序列是优美的,当且仅当存在 𝑘 ∈ [1, 𝑛],满足: 𝑥1 ≤ 𝑥2 ≤ … ≤ 𝑥𝑘 ≥ 𝑥𝑘+1 ≥ … ≥ 𝑥𝑛 。现在小 A 可以进行若干次操作,每次可以交换序列中相邻的两个项,现在他想知道最少操作多少次之后能够使序列变为优美的。

Input Format

第一行一个正整数 𝑛,表示序列的长度。 接下来一行 𝑛 个整数,表示初始的序列。

Output Format

输出一行一个整数,表示最少需要的操作次数。

Sample Input

5 3 4 1 2

Sample Output

1

Constraints

对于 30% 的数据,𝑛 ≤ 12。

对于 60% 的数据,𝑛 ≤ 100000, 𝑎𝑖 互不相同。

对于 100% 的数据,𝑛, 𝑎𝑖 ≤ 100000。

思路:

        仔细分析题意,因只能交换序列中相邻的两个项,且要求中间数大,两端较小。可以用贪心思想将每一个小的x[i]往左或往右两端移动,取最小的交换次数,最后累加即为所求。其实就是计算每个数左边或右边比它大的数(逆序对)有多少个,取最优。

        用树状数组刚好能满足快速计算逆序对的需求。注意:因数据有可能重复,我们需要将数组从大到小排序,且将数值相同的元素id大的往前放。

#include<bits/stdc++.h>
using namespace std;
int t[100005], n;
struct node {int x, id;
} a[100005], b[100005];
bool sort1(node a, node b) { //从大到小排序,值相同ID大的放前面if (a.x == b.x) return a.id > b.id;return a.x > b.x;
}
void add(int pos, int x) {while (pos <= n) {t[pos] += x;pos += -pos & pos;}
}
int sum(int pos) {int ans = 0;while (pos) {ans += t[pos];pos -= -pos & pos;}return ans;
}
int main() {int ans = 0;cin >> n;int resa[n + 1], resb[n + 1];for (int i = 1; i <= n; i++) {scanf("%d", &a[i].x);b[i].x = a[i].x;	//复制一个数组用于计算右边逆序对a[i].id = i;	//求i左边逆序对b[i].id = n - i + 1; //求i右边逆序对,id取反}sort(a + 1, a + 1 + n, sort1);sort(b + 1, b + 1 + n, sort1);for (int i = 1; i <= n; i++) {add(a[i].id, 1);resa[a[i].id] = sum(a[i].id - 1); //把每个i的逆序对保存到数组对应位置}memset(t, 0, sizeof(t)); //清空数组,以便计算右边逆序对for (int i = 1; i <= n; i++) {add(b[i].id, 1);resb[b[i].id] = sum(b[i].id - 1); }reverse(resb + 1, resb + 1 + n); //之前id是反向定义,需要反转数组元素for (int i = 1; i <= n; i++)ans += min(resa[i], resb[i]); //取每个i对于左右逆序对的最小值的和,即为所求cout << ans;return 0;
}

相关文章:

【CSP2019 模拟赛】Time

题目描述&#xff1a; 小 A 现在有一个长度为 &#x1d45b; 的序列 {&#x1d465;&#x1d456;}&#xff0c;但是小 A 认为这个序列不够优美。 小 A 认为一个序列是优美的&#xff0c;当且仅当存在 &#x1d458; ∈ [1, &#x1d45b;]&#xff0c;满足&#xff1a; &#…...

二叉树相关的算法题

二叉树相关的算法题 单值二叉树 如果二叉树每个节点都具有相同的值&#xff0c;那么该二叉树就是单值二叉树。 只有给定的树是单值二叉树时&#xff0c;才返回 true&#xff1b;否则返回 false。 示例 1&#xff1a; 输入&#xff1a;[1,1,1,1,1,null,1] 输出&#xff1a;t…...

Unity URP 曲面细分学习笔记

学百人时遇到了曲面着色器的内容&#xff0c;有点糊里糊涂&#xff0c;于是上知乎找到了两篇大佬的文章 Unity URP 曲面细分 和 Unity曲面细分笔记&#xff0c;本文只是自己做学习记录使用 1.曲面细分与镶嵌 曲面细分或细分曲面&#xff08;Subdivision surface&#xff09;是…...

每天五分钟深度学习pytorch:训练神经网络模型的基本步骤

本文重点 本文个人认为是本专栏最重要的章节内容之一,前面我们学习了pytorch中的基本数据tensor,后面我们就将学学习深度学习模型的内容了,在学习之前,我们先来看一下我们使用pytorch框架训练神经网络模型的基本步骤,然后我们下面就将这些步骤分解开来,详细学习。 代码…...

【langchain学习】使用缓存优化langchain中的LLM调用性能:内存、SQLite与Redis的对比

在处理语言模型(LLM)调用时,特别是在需要多次执行相同请求的情况下,缓存机制能够显著提升系统的性能。本文通过对比内存缓存(InMemoryCache)、SQLite缓存(SQLiteCache)和Redis缓存(RedisCache),探讨了如何在Langchain中使用这些缓存机制来优化LLM调用的性能。 代码…...

spring boot 集成EasyExcel

EasyExcel 是一个基于 Java 的快速、简洁的 Excel 处理工具&#xff0c;它能够在不用考虑性能和内存等因素的情况下&#xff0c;快速完成 Excel 的读写功能。 首先&#xff0c;需要在 Spring Boot 项目中引入 EasyExcel 依赖。在 pom.xml 文件中添加以下依赖&#xff1a; <d…...

获取对象中第一个存在的值

在JavaScript中&#xff0c;要从一个对象中获取第一个存在的&#xff08;非undefined、非null、非空数组等&#xff09;值&#xff0c;你可以使用Object.values()方法结合Array.prototype.find()方法。以下是一个示例代码&#xff0c;演示如何实现这一点&#xff1a; const ob…...

Python学习笔记----集合与字典

1. 字符串、列表和元组的元素都是按下标顺序排列&#xff0c;可通过下 标直接访问&#xff0c;这样的数据类型统称为序列。 其中&#xff0c;字符串和元组中的元素不能修改&#xff0c;而列表中的元素可以修改。 集合 1. 与元组和列表类似&#xff0c;Set &#xff08;集合&a…...

c# 排序、强转枚举

List<Tuple<double,int>> mm中doble从小到大排序 mm本身排序 在C#中&#xff0c;如果你有一个List<Tuple<double, int>>类型的集合mm&#xff0c;并且你想要根据Tuple中的double值&#xff08;即第一个元素&#xff09;从小到大进行排序&#xff0c;同…...

“华为杯”第十六届中国研究生数学建模竞赛-C题:视觉情报信息分析

目录 摘 要: 一、问题重述 二、模型假设 三、符号说明 四、问题一分析与求解 4.1 问题一分析 4.2 模型建立 4.2.1 位置变换模型建立 4.2.4 多平面转换模型建立 4.3 模型求解 4.3.1 问题一图 1 结果 4.3.2 问题一图 2 结果 4.3.3 问题一图 3 结果 4.3.4 问题一图 4 结果 4.4 模…...

html+css+js网页设计 找法网2个页面(带js)ui还原度百分之90

htmlcssjs网页设计 找法网2个页面&#xff08;带js&#xff09;ui还原度百分之90 网页作品代码简单&#xff0c;可使用任意HTML编辑软件&#xff08;如&#xff1a;Dreamweaver、HBuilder、Vscode 、Sublime 、Webstorm、Text 、Notepad 等任意html编辑软件进行运行及修改编辑…...

018 | backtrader回测反转策略

什么是反转策略&#xff1f; 反转策略&#xff08;Reversal Strategy&#xff09;是一种试图捕捉市场价格趋势逆转的交易策略。与趋势跟随策略不同&#xff0c;反转策略的核心理念是“物极必反”&#xff0c;即价格在经过一段时间的单边趋势后&#xff0c;往往会出现逆转的机会…...

《图解HTTP》全篇目录

前言 目前&#xff0c;国内讲解 HTTP 协议的书实在太少了。在我的印象中&#xff0c;讲解网络协议的书仅有两本。一本是《HTTP 权威指南》&#xff0c;但其厚度令人望而生畏&#xff1b;另一本是《TCP/IP 详解&#xff0c;卷 1》&#xff0c;内容艰涩难懂&#xff0c;学习难度…...

基于VS2019(Release_x64)+Qt的软件开发—环境配置

前置博客&#xff1a; 基于C高级编程语言的软件开发随记——环境变量-CSDN博客 &#xff08;一&#xff09;一种避免设置大量环境变量的VS2019环境配置方法 Ⅰ 解决方案资源管理器->VC目录->在包含目录/库目录中添加对应的include/lib文件夹&#xff08;$&#xff08;So…...

【书生大模型实战营(暑假场)闯关材料】入门岛:第1关 Linux 基础知识

【书生大模型实战营&#xff08;暑假场&#xff09;闯关材料】入门岛&#xff1a;第1关 Linux 基础知识 1. 使用VScode进行SSH远程连接服务器2. 端口映射及实例参考文献 这一博客主要介绍使用VScode进行服务器远程连接及端口映射。 1. 使用VScode进行SSH远程连接服务器 安装V…...

240810-Gradio通过HTML组件打开本地文件+防止网页跳转到about:blank

A. 最终效果 B. 可通过鼠标点击打开文件&#xff0c;但会跳转到about:blank import gradio as gr import subprocessdef open_pptx():pptx_path /Users/liuguokai/Downloads/240528-工业大模型1.pptxtry:subprocess.Popen([open, pptx_path])return "PPTX file opened s…...

go在linux上安装

1.首先要确定Linux架构 uname -m如果你的系统是 armv7l&#xff08;32-bit ARM&#xff09;&#xff0c;你需要下载 armv6l 版的Go语言。 如果你的系统是 aarch64&#xff08;64-bit ARM&#xff09;&#xff0c;你需要下载 arm64 版的Go语言。 如果你的系统是 x86_64&#xf…...

算法日记day 35(动归之分割等和子集|最后一块石头的重量2)

一、分割等和子集 题目&#xff1a; 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集&#xff0c;使得两个子集的元素和相等。 示例 1&#xff1a; 输入&#xff1a;nums [1,5,11,5] 输出&#xff1a;true 解释&#xff1a;数组可以分…...

FPGA使用sv生成虚拟单音数据

FPGA使用sv生成虚拟单音数据 之前一直使用matlab生成虚拟的数据&#xff0c;导出到txt或是coe文件中&#xff0c;再导入到fpga中进行仿真测试。 复杂的数据这样操作自然是必要的&#xff0c;但是平日使用正弦数据进行测试的话&#xff0c;这样的操作不免复杂&#xff0c;今日…...

Linux shell编程:监控进程CPU使用率并使用 perf 抓取高CPU进程信息

0. 概要 本文将介绍一个用于监控一组进程CPU使用率的Shell脚本&#xff0c;&#xff0c;当检测到某进程的CPU使用率超出阈值时&#xff0c;使用 perf 工具抓取该进程的详细信息。 本shell脚本为了能在普通嵌入式系统上运行做了妥协和优化。 1. shell脚本流程的简要图示&#…...

SMR实战:如何将GWAS数据快速转换为BESD格式(附常见错误排查)

SMR实战&#xff1a;GWAS数据高效转换为BESD格式的完整指南与深度排错手册 在生物信息学研究中&#xff0c;基于汇总数据的孟德尔随机化&#xff08;Summary-data-based Mendelian Randomization, SMR&#xff09;已成为探索基因表达数量性状位点&#xff08;eQTL&#xff09;与…...

如何通过霞鹜文楷解决中文开源字体在技术项目中的核心挑战

如何通过霞鹜文楷解决中文开源字体在技术项目中的核心挑战 【免费下载链接】LxgwWenKai An unprofessional open-source Chinese font derived from Fontworks Klee One. 一款非专业的开源中文字体&#xff0c;基于 FONTWORKS 出品字体 Klee One 衍生。 项目地址: https://g…...

计算机毕业设计springboot智慧化教学辅助系统 基于SpringBoot的智能化教学管理与评价平台 SpringBoot驱动的数字化教学支持服务平台

计算机毕业设计springboot智慧化教学辅助系统 &#xff08;配套有源码 程序 mysql数据库 论文&#xff09; 本套源码可以在文本联xi,先看具体系统功能演示视频领取&#xff0c;可分享源码参考。随着信息技术的迅猛发展和全球教育环境的不断变化&#xff0c;传统教育模式正面临着…...

3步突破AI编程助手限制:免费解锁Cursor Pro高级功能全指南

3步突破AI编程助手限制&#xff1a;免费解锁Cursor Pro高级功能全指南 【免费下载链接】cursor-free-vip [Support 0.45]&#xff08;Multi Language 多语言&#xff09;自动注册 Cursor Ai &#xff0c;自动重置机器ID &#xff0c; 免费升级使用Pro 功能: Youve reached your…...

还在用老掉牙的HashTab?2024年最新文件哈希校验工具横向评测(附下载)

2024年文件哈希校验工具终极指南&#xff1a;告别过时方案&#xff0c;拥抱高效验证 还在为文件完整性验证发愁&#xff1f;每次下载重要软件都要反复核对哈希值却找不到趁手工具&#xff1f;作为从业十年的信息安全顾问&#xff0c;我见证了哈希校验工具从简陋到专业的演变。今…...

从ONNX到TPU:跨框架模型部署的编译器避坑指南(2023最新版)

从ONNX到TPU&#xff1a;跨框架模型部署的编译器避坑指南&#xff08;2023最新版&#xff09; 当ResNet模型在PyTorch中达到99%的测试准确率时&#xff0c;真正的挑战才刚刚开始——如何让这个模型在边缘设备的TPU芯片上高效运行&#xff1f;这个问题困扰着85%的AI工程师。本文…...

WarcraftHelper:魔兽争霸III性能优化终极指南 - 10分钟打造完美游戏体验

WarcraftHelper&#xff1a;魔兽争霸III性能优化终极指南 - 10分钟打造完美游戏体验 【免费下载链接】WarcraftHelper Warcraft III Helper , support 1.20e, 1.24e, 1.26a, 1.27a, 1.27b 项目地址: https://gitcode.com/gh_mirrors/wa/WarcraftHelper 魔兽争霸III作为经…...

如何突破Cursor AI编程助手的使用限制:技术原理与实践指南

如何突破Cursor AI编程助手的使用限制&#xff1a;技术原理与实践指南 【免费下载链接】cursor-free-vip [Support 0.45]&#xff08;Multi Language 多语言&#xff09;自动注册 Cursor Ai &#xff0c;自动重置机器ID &#xff0c; 免费升级使用Pro 功能: Youve reached your…...

幻兽帕鲁存档迁移完全手册:告别数据丢失的终极解决方案

幻兽帕鲁存档迁移完全手册&#xff1a;告别数据丢失的终极解决方案 【免费下载链接】palworld-host-save-fix 项目地址: https://gitcode.com/gh_mirrors/pa/palworld-host-save-fix 你是否曾在更换幻兽帕鲁服务器时&#xff0c;眼睁睁看着自己辛苦培养的角色数据消失无…...

告别重复劳动:用快马AI智能生成OpenCode风格的高效工具函数

最近在开发一个需要大量表单验证的项目时&#xff0c;我发现每次都要重复写类似的验证逻辑&#xff0c;既浪费时间又容易出错。于是我开始寻找更高效的解决方案&#xff0c;最终在InsCode(快马)平台上找到了理想的工具。 需求分析 表单验证是每个Web项目都绕不开的基础功能。常…...