hdu4911 简单树状数组
数组 简单 树状
2023-09-11 14:14:00 时间
题意:
给你一串数字,然后给你最多进行k次交换(只能交换相邻的)问交换后的最小逆序数是多少。
思路:
给你一串数字,然后给你最多进行k次交换(只能交换相邻的)问交换后的最小逆序数是多少。
思路:
首先要知道的一个就是给你一个序列,每次只能交换相邻的位置,把他交换成一个递增序列所需要的最少步数等于整个序列的逆序数,在转化到这个题目,我们只要求出个逆序数,然后输出逆序数 - k就行了,如果是负数输出0。
#include<stdio.h> #include<string.h> #include<algorithm> #define N 100000 + 10 using namespace std; typedef struct { int num ,id; }NODE; NODE node[N]; __int64 num[N]; int hash[N]; int lowbit(int x) { return x & -x; } void update(int x ,__int64 a ,int n) { for(int i = x ;i <= n ;i += lowbit(i)) num[i] += a; } __int64 find(int x) { __int64 sum = 0; for(int i = x ;i > 0 ;i -= lowbit(i)) sum += num[i]; return sum; } bool camp(NODE a ,NODE b) { return a.num < b.num; } int main () { int n ,i ,a; __int64 m ,sum; while(~scanf("%d %I64d" ,&n ,&m)) { for(i = 1 ;i <= n ;i ++) { scanf("%d" ,&node[i].num); node[i].id = i; } sort(node + 1 ,node + n + 1 ,camp); int t = 0; node[0].num = -1; for(i = 1 ;i <= n; i ++) { if(node[i].num != node[i-1].num) t ++; hash[node[i].id] = t; } memset(num ,0 ,sizeof(num)); for(sum = 0 ,i = 1 ;i <= n ;i ++) { sum += (i - 1) - find(hash[i]); update(hash[i] ,1 ,t); } if(sum < m) printf("0\n"); else printf("%I64d\n" ,sum - m); } return 0; }
相关文章
- php 通过array_merge()和array+array合并数组的区别和效率比较
- 线性表结构:数组
- json 字符串包含数组转换为object对象是报异常java.lang.ClassCastException: net.sf.ezmorph.bean.MorphDynaBean cannot be cast to
- C#中list比数组效率低多少
- java实现第六届蓝桥杯九数组分数
- js中数组的splice()方法
- 使用Sort方法对数组进行快速排序
- Python简单计算数组元素平均值的方法示例
- 【数组&双指针】leetcode 234. 回文链表【简单】
- 【数组&双指针】LeetCode 1. 两数之和【简单】
- Java基础篇4——数组
- 737. 数组替换
- Atiitt io的stream流的分类 目录 1. 流的优缺点 高性能但复杂1 1.1. 字节数组更加简单,但性能差点1 2. Io体系1 2.1. 字符流 vs 字节流2 2.2.
- 【LeetCode 简单 数组 python3】27. 移除元素
- 【LeetCode Python实现】26. 删除排序数组中的重复项(简单)
- 【LeetCode 简单 排序 python3】349. 两个数组的交集
- 1191. K 次串联后最大子数组之和-暴力动态规划,和优化算法
- Leetcode2248. 多个数组求交集(map轻松求交集问题)
- VB编程:利用数组实现矩阵转换-28
- 动态规划典型例题--连续子数组的最大和
- 简单方法快速记忆数组栈和队列函数
- HDU-4031-Attack(树状数组)
- 二分法应用——搜索旋转数组,以前一直在纠结a[0],a[-1],a[mid], target三者关系,其实最简单的还是使用2次二分,先找到旋转数组peak,然后用正常的二分搜索即可!
- wukong引擎源码分析之搜索——docid有序的数组里二分归并求交集,如果用跳表的话,在插入索引时会更快
- OpenCV这么简单为啥不学——1.2、图片截取(数组截取)
- 数组专题~有人十八单手开法拉利,有人二十加在lc刷算法题
- MATLAB 学习笔记(4)MATLAB 数组