http://acm.hdu.edu.cn/showproblem.php?pid=1394

2024-01-10 07:48

本文主要是介绍http://acm.hdu.edu.cn/showproblem.php?pid=1394,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

树状数组求逆序数的应用。。这一题设计的非常巧妙。。。下面说一下题意。。给定一组数,然后依次的挪动该组数的元素共得到n种序列。求这n中序列中逆序数最少的个数。。。杯具的是我竟然把树状数组和一般的数组弄混淆了。。这里要特别注意。。。不过值得一提的是竟然rank1,(*^__^*) 嘻嘻……

AC代码:

#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#define N 5005
using namespace std;
int s[N];
int kp[N];
int n;
int lowbit(int x)
{return x&(-x);}
void update(int x)
{   while(x<=n){  s[x]++; x+=lowbit(x);}
}
int Quary(int x)
{ int sum=0;while(x>0){  sum+=s[x];x-=lowbit(x);}return sum;
}
int main()
{   while(~scanf("%d",&n)){   int res=0;memset(s,0,sizeof(s));memset(kp,0,sizeof(kp));for(int i=1;i<=n;++i){   scanf("%d",&kp[i]);kp[i]++;update(kp[i]);res+=i-Quary(kp[i]);}int minn=res;for(int i=n;i>=2;--i){ res+=2*kp[i]-n-1;//每移动一次增加kp[i]-1个逆序数,同时减少n-kp[i]个逆序数。。。minn=min(minn,res);}printf("%d\n",minn);}return 0;
}


这篇关于http://acm.hdu.edu.cn/showproblem.php?pid=1394的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

Linux中修改Apache HTTP Server(httpd)默认端口的完整指南

《Linux中修改ApacheHTTPServer(httpd)默认端口的完整指南》ApacheHTTPServer(简称httpd)是Linux系统中最常用的Web服务器之一,本文将详细介绍如何... 目录一、修改 httpd 默认端口的步骤1. 查找 httpd 配置文件路径2. 编辑配置文件3. 保存

C++ HTTP框架推荐(特点及优势)

《C++HTTP框架推荐(特点及优势)》:本文主要介绍C++HTTP框架推荐的相关资料,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. Crow2. Drogon3. Pistache4. cpp-httplib5. Beast (Boos

SpringBoot中HTTP连接池的配置与优化

《SpringBoot中HTTP连接池的配置与优化》这篇文章主要为大家详细介绍了SpringBoot中HTTP连接池的配置与优化的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录一、HTTP连接池的核心价值二、Spring Boot集成方案方案1:Apache HttpCl

Spring Boot Controller处理HTTP请求体的方法

《SpringBootController处理HTTP请求体的方法》SpringBoot提供了强大的机制来处理不同Content-Type​的HTTP请求体,这主要依赖于HttpMessageCo... 目录一、核心机制:HttpMessageConverter​二、按Content-Type​处理详解1.

Nginx中配置HTTP/2协议的详细指南

《Nginx中配置HTTP/2协议的详细指南》HTTP/2是HTTP协议的下一代版本,旨在提高性能、减少延迟并优化现代网络环境中的通信效率,本文将为大家介绍Nginx配置HTTP/2协议想详细步骤,需... 目录一、HTTP/2 协议概述1.HTTP/22. HTTP/2 的核心特性3. HTTP/2 的优

使用Python自建轻量级的HTTP调试工具

《使用Python自建轻量级的HTTP调试工具》这篇文章主要为大家详细介绍了如何使用Python自建一个轻量级的HTTP调试工具,文中的示例代码讲解详细,感兴趣的小伙伴可以参考一下... 目录一、为什么需要自建工具二、核心功能设计三、技术选型四、分步实现五、进阶优化技巧六、使用示例七、性能对比八、扩展方向建

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

Go语言中最便捷的http请求包resty的使用详解

《Go语言中最便捷的http请求包resty的使用详解》go语言虽然自身就有net/http包,但是说实话用起来没那么好用,resty包是go语言中一个非常受欢迎的http请求处理包,下面我们一起来学... 目录安装一、一个简单的get二、带查询参数三、设置请求头、body四、设置表单数据五、处理响应六、超

如何使用Docker部署FTP和Nginx并通过HTTP访问FTP里的文件

《如何使用Docker部署FTP和Nginx并通过HTTP访问FTP里的文件》本文介绍了如何使用Docker部署FTP服务器和Nginx,并通过HTTP访问FTP中的文件,通过将FTP数据目录挂载到N... 目录docker部署FTP和Nginx并通过HTTP访问FTP里的文件1. 部署 FTP 服务器 (

Qt实现发送HTTP请求的示例详解

《Qt实现发送HTTP请求的示例详解》这篇文章主要为大家详细介绍了如何通过Qt实现发送HTTP请求,文中的示例代码讲解详细,具有一定的借鉴价值,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、添加network模块2、包含改头文件3、创建网络访问管理器4、创建接口5、创建网络请求对象6、创建一个回复对