http://acm.hdu.edu.cn/showproblem.php?pid=2838逆序数的应用

2024-01-10 07:48

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

这算是一道比较综合的树状数组题。。

题意:一个农场主养了很多奶牛,每天晚上该农场主都要为奶牛,但是每个奶牛都有一个脾气,这可能会导致奶牛损坏农场主喂牛的工具。。每个奶牛的脾气不等,这样农场主可以调换的某两个牛的位置,以求奶牛破坏最少的工具。已知挪动两个奶牛花费的时间为两个奶牛脾气的和。。让你求出最少的时间在破坏最少工具的前提下。。

思路:树状数组中有两个元素一个是记录比当前a小的个数,一个是记录比当前a小的数的和。。mintime=a*(i-Quary_cnt(a))+Quary_sum(n)-Quary_sum(a);







#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#define M 100001
using namespace std;
typedef long long L;
int n;
typedef struct str
{ int cnt;L sum;
}Node;
Node s[M];
inline int lowbit(int x)
{return x&(-x);}
void update(int x,int y)
{  while(x<=n){  s[x].sum+=y;s[x].cnt++;x+=lowbit(x);}
}
L Quary_sum(int x)
{ L  res=0;while(x>0){  res+=s[x].sum;x-=lowbit(x);}return res;
}
L Quary_cnt(int x)
{ L res=0;while(x>0){  res+=s[x].cnt;x-=lowbit(x);}return res;
}
int main()
{   while(~scanf("%d",&n)){    memset(s,0,sizeof(s));int a;L s1=0;for(int i=1;i<=n;++i){  scanf("%d",&a);update(a,a);L res=i-Quary_cnt(a);//求逆序数的个数if(res!=0){   L k=Quary_sum(n)-Quary_sum(a);//比a大的所有元素的和s1+=(k+res*a);}}printf("%I64d\n",s1);}return 0;
}


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



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

相关文章

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

springboot如何通过http动态操作xxl-job任务

《springboot如何通过http动态操作xxl-job任务》:本文主要介绍springboot如何通过http动态操作xxl-job任务的问题,具有很好的参考价值,希望对大家有所帮助,如有错... 目录springboot通过http动态操作xxl-job任务一、maven依赖二、配置文件三、xxl-

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 注解方式 基础使用自定义重试策略失败恢复机制注意事项

Maven 配置中的 <mirror>绕过 HTTP 阻断机制的方法

《Maven配置中的<mirror>绕过HTTP阻断机制的方法》:本文主要介绍Maven配置中的<mirror>绕过HTTP阻断机制的方法,本文给大家分享问题原因及解决方案,感兴趣的朋友一... 目录一、问题场景:升级 Maven 后构建失败二、解决方案:通过 <mirror> 配置覆盖默认行为1. 配置示

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

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

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

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

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

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