首页 > 其他分享 >逆序对的数量

逆序对的数量

时间:2024-10-24 11:13:08浏览次数:4  
标签:count int sum mid long ++ 数量 逆序

#include<iostream>
using namespace std;
int num[100010], temp[100010];
long long count( int l , int r){
    if(l >= r) return 0;
    
    long long sum = 0;
    int mid = (l + r) >> 1;
    
    sum += count(l , mid);
    sum += count(mid + 1 , r);
    
    for(int i = l , j = mid + 1; i <= mid && j <= r; ){
        if(num[i] > num[j]) {
            sum += mid - i + 1;
            j ++;
        }
        else i ++;
    }
    
    int i = l , j = mid + 1 , k = 0;
    while(i <= mid && j <= r){
        if(num[i] <= num[j]) temp[k ++] = num[i ++];
        else temp[k ++] = num[j ++]; 
    }
    while(i <= mid) temp[k ++] = num[i ++];
    while(j <= r) temp[k ++] = num[j ++];
    
    for(int i = l , j = 0 ; j < k ; j ++ , i ++) num[i] = temp[j];
    
    return sum;
}

int main(){
    int n ; 
    cin >> n;
    
    for(int i = 0 ; i < n ; i ++) cin >> num[i];
    
    cout << count(0 , n - 1) << endl;
    
    return 0;
}

标签:count,int,sum,mid,long,++,数量,逆序
From: https://www.cnblogs.com/lxy54/p/18499217

相关文章

  • 代码随想录算法训练营 | 岛屿数量 深搜,岛屿数量 广搜,岛屿的最大面积
    岛屿数量深搜题目链接:岛屿数量深搜文档讲解︰代码随想录(programmercarl.com)日期:2024-10-23想法:Java代码如下:importjava.util.Scanner;publicclassMain{publicstaticint[][]dir={{0,1},{1,0},{-1,0},{0,-1}};publicstaticvoiddfs(boolean[][]v......
  • PCC Net模型实现行人数量统计
    关注底部公众号,回复暗号:13,免费获取600多个深度学习项目资料,快来加入社群一起学习吧。项目简介PCCNet是一种用于拥挤场景下行人计数的深度学习模型。该项目的目标是利用神经网络,准确地统计给定区域内的行人数,输入可以是图像或视频帧。行人计数广泛应用于交通管理、活动......
  • 在K8S中,有一家拼车公司希望通过同时扩展其平台来增加服务器数量,公司如何有效地实现这
    在Kubernetes(K8S)中,对于一家拼车公司希望通过同时扩展其平台来增加服务器数量以实现有效的资源分配,可以按照以下步骤进行:1.准备阶段评估需求:拼车公司需要明确其业务增长预期、用户访问量、峰值负载等关键指标,以确定所需的服务器数量和资源配置。规划架构:设计一个可扩展......
  • [Python手撕]游戏中弱角色的数量
    你正在参加一个多角色游戏,每个角色都有两个主要属性:攻击和防御。给你一个二维整数数组properties,其中properties[i]=[attacki,defensei]表示游戏中第i个角色的属性。如果存在一个其他角色的攻击和防御等级都严格高于该角色的攻击和防御等级,则认为该角色为弱角色......
  • Linux文件实时自动同步方案(基于inotify) 支持自定义目录、 不限主机数量、支持增删改
    实现细节可以直接跳到第3节3.实现细节关键词:自动同步Linux自动同步 Linux实时同步master同步slave master与slave文件实时同步 目录1.引言背景介绍方案概述方案特点2.技术选型inotifyrsyncShell脚本3.实现细节3.1前置配置1.权限设置2.安装inotify......
  • [算法日常] 逆序对
    [算法日常]逆序对定义在一个长度为\(n\)的数组\(a\)中,若存在\(\forall1\lei,j\len\),使得\(a_i>a_j\),则称\(<a_i,a_j>\)为一对逆序对。举个例子,一个长度为\(5\)的数组为:15364则存在\(3\)个逆序对,分别是\(<5,3>,<5,4>,<6,4>\)。解法F1:显然,可以枚举......
  • 比较相同机器上 redis和mysql分别单独承载的 最大连接数量
    在相同的机器上,Redis和MySQL的最大连接数量会受到硬件配置(如CPU、内存、网络等)、配置参数和应用场景的影响。以下是对Redis和MySQL在单机环境下最大连接数的比较:Redis最大连接数量默认配置:Redis默认的最大连接数为10,000。这个值可以通过配置文件中的maxcl......
  • 岛屿数量(深度优先遍历)
    给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外,你可以假设该网格的四条边均被水包围。示例1:输入:grid=[["1","1","1","1","0"],["1","1",&qu......
  • 后台发货动态校验多包裹及校验可选择发货数量
    之前通过多级动态表单获取到多包裹,接下来就是再根据多包裹来判断可选择发货数量要结合之前的多级表单动态添加包裹会更好理解目前这个只是一种方法,我相信还有别的方法,可能会更简单选择商品选择商品里面选择可选择发货数量,可选择的发货数量是总数量-每个包裹选择的当前商品......
  • JavaScript 实现购物车数量增加减少功能
    场景描述在实现购物车功能时,需要限制用户加购的数量必须大于0且不超过加购商品的库存量。代码实现下列代码中,<input></input>中使用min属性定义数量的最小值,max属性定义数量的最大值。在实际开发中可以整合springboot和thymeleaf,使用th:max="${商品对象的库存量}"将ma......