HDU 1394 Minimum Inversion Number (树状数组 && 规律 && 逆序数)
2024-08-30 09:59:38
题意 : 有一个n个数的数列且元素都是0~n-1,问你将数列的其中某一个数及其前面的数全部置到后面这种操作中(比如3 2 1 0中选择第二个数倒置就产生1 0 3 2)能产生的最少的逆序数对是多少?
分析 : 首先铁定排除枚举法,直接暴力肯定是超时的。既然这样不妨来找找规律,从第一个数开始,如果我们将第一个数放到末尾,根据逆序数的特点,能够推断出当前总逆序数应该是减少了arr[i]并增加了(n-1)-arr[i] (这里arr[i]代表这个数后面有多少个数小于它),如果细心一点,可以发现不管是从第几个数开始,都是由我们刚刚所说的将第一个数放到末尾构造而来,比如 1 2 3 4 我们将第二个数开始放到末尾就是 3 4 1 2,同样是可以这样构造而来,就是先将第一个数放到末尾产生一个序列 2 3 4 1,然后又进行一次将第一个数放到末尾产生3 4 1 2,这样根据我们之前得到的结论,只要知道当前序列的逆序数对和arr[i],我们就能递推出下一个序列的逆序数对。那么现在关键就是arr[i]怎么快速求?还记得序列是个0~n-1的序列嘛,实际上arr[i]就等于当前在头部的这个数的值,比如 2 1 3 0 在头部的是2,那么后面就有2个比它小的数!所以最终要得到答案我们只要一开始算出原始序列的逆序数对就能够O(n)的枚举了!
#include<bits/stdc++.h> #define lowbit(i) (i&(-i)) using namespace std; ; int c[maxn]; int top, n; void add(int i, int val) { while(i <= n){ c[i] += val; i += lowbit(i); } } int sum(int i) { ; ){ ret += c[i]; i -= lowbit(i); } return ret; } int arr[maxn]; int main(void) { while(~scanf("%d", &n)){ top = n; memset(c, , sizeof(c)); memset(arr, 0x3f, sizeof(arr)); ; ; i<n; i++){ int tmp; scanf("%d", &arr[i]); arr[i]+=;//树状数组小心0的陷阱! SUM += i - sum(arr[i]);//累计求出初始序列的逆序数对 add(arr[i], ); } int ans = SUM; ; i<n; i++){ ans = min(SUM, ans); SUM += n - arr[i] - (arr[i] - );//递推构造 } printf("%d\n", ans); } ; }
瞎 : 面对这种操作很明显有规律的,就要赶快先实验前几次操作,找找规律,再想想能不能递推,题目给出的序列的任何一个性质都是有用的,比如这里的0~n-1,以后遇到类似的题就把能得到的性质全部列出来,把每一步操作能得到的结果和特点综合分析,不能瞎想.....
最新文章
- 雅虎(yahoo)前端优化十四条军规
- notepad++
- JAVA EE中session的理解
- openjudge2989糖果[DP 01背包可行性]
- RH LINUX5.5 RAW绑定
- 关于php一句话免杀的分析<;转载>;
- 分页SQL技术1-COUNT STOPKEY.
- DC DC電路電感的選擇
- Delphi TcxTreeList 读取 TcxImageComboBoxItem类型的值
- android离线下载的相关知识
- oracle 时间比较查询
- 在CodeBlocks 开发环境中配置使用OpenCV (ubuntu系统)
- Java继承多态中的方法访问权限控制
- 1042 数字0-9的数量 1050 循环数组最大子段和 1062 序列中最大的数 1067 Bash游戏 V2 1092 回文字符串
- 啥?客户叫在DataGridView的左上角添加CheckBox?
- hibernate的lazy初始化结果
- java中解析excel 批量插入数据库
- 6.26 py GIL
- lua --- dofile、loadfile、require
- Python返回值不同格式的取值方式