hdu1394(线段树点更新的应用)

2024-09-09 17:32

本文主要是介绍hdu1394(线段树点更新的应用),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:求一个序列经过一定的操作得到的序列的最小逆序数

这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1)

知道上面的知识点后,可以用暴力来解

代码如下:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define N 50005
#define inf 0x7ffffff
#define eps 1e-9
#define pi acos(-1.0)
#define P system("pause")
using namespace std;
int a[N],num[N];
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);int n;while(scanf("%d",&n) != EOF){int i, j;for(i = 0; i < n; i++)scanf("%d",&a[i]);memset(num,0,sizeof(num));int res = 0;for(i = 1; i < n; i++){for(j = 0; j < i; j++)if(a[i] < a[j])num[i]++;res += num[i];}int minn = res;for(i = 0; i < n-1; i++){res = res-a[i]+n-1-a[i];//cout<<res<<endl;if(res < minn) minn = res;}printf("%d\n",minn);}return 0;
}
但是这题用线段树解,时间可以优化很多

思路入下:

这里的线段树只用来求逆序数,依次输入一个数据a,a所在的区间都加1,然后查询[ a , n ]上的sum,这就是a的逆序数

为了方便理解,最好自己举个例子

代码如下:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define N 50005
#define inf 0x7ffffff
#define eps 1e-9
#define pi acos(-1.0)
#define P system("pause")
using namespace std;
int a[N],c[N];
struct node
{int l,r,sum;
}tree[N*4];
int res;
void build(int o,int l,int r)
{tree[o].l = l;tree[o].r = r;if(l == r){tree[o].sum = 0;return ;}int m = (l + r)/2;build(2*o,l,m);build(2*o+1,m+1,r);tree[o].sum = tree[2*o].sum + tree[2*o+1].sum;
}
void insert(int o,int k)
{if(tree[o].l == tree[o].r){tree[o].sum = 1;return;}int m = (tree[o].l+tree[o].r)/2;if(k <= m) insert(2*o,k);if(k > m) insert(2*o+1,k);tree[o].sum = tree[2*o].sum + tree[2*o+1].sum;
}
void query(int o,int x,int y)
{if(x <= tree[o].l && tree[o].r <= y){res += tree[o].sum;return;}int m = (tree[o].l + tree[o].r)/2;if(x <= m)query(2*o,x,y);if(y > m)query(2*o+1,x,y);
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);int n;while(scanf("%d",&n) != EOF){int i,ans = 0;build(1,1,n);for(i = 0; i < n; i++){scanf("%d",&a[i]);insert(1,a[i]+1);res = 0;query(1,a[i]+2,n);c[i] = res;ans += c[i];}int minn = ans;//cout<<ans<<endl;for(i = 0; i < n-1; i++)//把n-1个数字依此移到最后{ans = ans - a[i] + (n-a[i]-1);//每个数依此移到最后得到的逆序数//  cout<<ans<<endl;if(minn > ans)minn = ans;}printf("%d\n",minn);}return 0;
}








这篇关于hdu1394(线段树点更新的应用)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1151816

相关文章

PostgreSQL的扩展dict_int应用案例解析

《PostgreSQL的扩展dict_int应用案例解析》dict_int扩展为PostgreSQL提供了专业的整数文本处理能力,特别适合需要精确处理数字内容的搜索场景,本文给大家介绍PostgreS... 目录PostgreSQL的扩展dict_int一、扩展概述二、核心功能三、安装与启用四、字典配置方法

Python中re模块结合正则表达式的实际应用案例

《Python中re模块结合正则表达式的实际应用案例》Python中的re模块是用于处理正则表达式的强大工具,正则表达式是一种用来匹配字符串的模式,它可以在文本中搜索和匹配特定的字符串模式,这篇文章主... 目录前言re模块常用函数一、查看文本中是否包含 A 或 B 字符串二、替换多个关键词为统一格式三、提

Java MQTT实战应用

《JavaMQTT实战应用》本文详解MQTT协议,涵盖其发布/订阅机制、低功耗高效特性、三种服务质量等级(QoS0/1/2),以及客户端、代理、主题的核心概念,最后提供Linux部署教程、Sprin... 目录一、MQTT协议二、MQTT优点三、三种服务质量等级四、客户端、代理、主题1. 客户端(Clien

MySQL追踪数据库表更新操作来源的全面指南

《MySQL追踪数据库表更新操作来源的全面指南》本文将以一个具体问题为例,如何监测哪个IP来源对数据库表statistics_test进行了UPDATE操作,文内探讨了多种方法,并提供了详细的代码... 目录引言1. 为什么需要监控数据库更新操作2. 方法1:启用数据库审计日志(1)mysql/mariad

CSS中的Static、Relative、Absolute、Fixed、Sticky的应用与详细对比

《CSS中的Static、Relative、Absolute、Fixed、Sticky的应用与详细对比》CSS中的position属性用于控制元素的定位方式,不同的定位方式会影响元素在页面中的布... css 中的 position 属性用于控制元素的定位方式,不同的定位方式会影响元素在页面中的布局和层叠关

SpringBoot3应用中集成和使用Spring Retry的实践记录

《SpringBoot3应用中集成和使用SpringRetry的实践记录》SpringRetry为SpringBoot3提供重试机制,支持注解和编程式两种方式,可配置重试策略与监听器,适用于临时性故... 目录1. 简介2. 环境准备3. 使用方式3.1 注解方式 基础使用自定义重试策略失败恢复机制注意事项

Python使用Tkinter打造一个完整的桌面应用

《Python使用Tkinter打造一个完整的桌面应用》在Python生态中,Tkinter就像一把瑞士军刀,它没有花哨的特效,却能快速搭建出实用的图形界面,作为Python自带的标准库,无需安装即可... 目录一、界面搭建:像搭积木一样组合控件二、菜单系统:给应用装上“控制中枢”三、事件驱动:让界面“活”

如何确定哪些软件是Mac系统自带的? Mac系统内置应用查看技巧

《如何确定哪些软件是Mac系统自带的?Mac系统内置应用查看技巧》如何确定哪些软件是Mac系统自带的?mac系统中有很多自带的应用,想要看看哪些是系统自带,该怎么查看呢?下面我们就来看看Mac系统内... 在MAC电脑上,可以使用以下方法来确定哪些软件是系统自带的:1.应用程序文件夹打开应用程序文件夹

Python Flask 库及应用场景

《PythonFlask库及应用场景》Flask是Python生态中​轻量级且高度灵活的Web开发框架,基于WerkzeugWSGI工具库和Jinja2模板引擎构建,下面给大家介绍PythonFl... 目录一、Flask 库简介二、核心组件与架构三、常用函数与核心操作 ​1. 基础应用搭建​2. 路由与参

Spring Boot中的YML配置列表及应用小结

《SpringBoot中的YML配置列表及应用小结》在SpringBoot中使用YAML进行列表的配置不仅简洁明了,还能提高代码的可读性和可维护性,:本文主要介绍SpringBoot中的YML配... 目录YAML列表的基础语法在Spring Boot中的应用从YAML读取列表列表中的复杂对象其他注意事项总