HDU-1394 Minimum Inversion Number (逆序数,线段树或树状数组)
2024-09-05 21:49:38
The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj.
For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:
a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)
You are asked to write a program to find the minimum inversion number out of the above sequences.
For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:
a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)
You are asked to write a program to find the minimum inversion number out of the above sequences.
10
1 3 6 9 0 8 5 7 4 2
16
逆序数,就是你比人家小,结果还在人家后边。。。可以用线段树或树状数组求,每一次出现一个数,设为a,就求一次a到n之间的和,也就是比a大却先比a出现的数字个数,然后把a的位置标记为一,其余几次的逆序数可以直接推导出来,设第一次移动的数为a,把它移动到后面理论上会减少a个逆序数(注意从0开始),但是还会有n-1-a个数大于a,所以sum+=n-1-2*a;
线段树:
zkw线段树:
最新文章
- input框focus时的美化效果
- Shell脚本检测文件夹是否已被挂载的方法
- Java 对象序列化(Serialization Object)
- The model backing the <;Database>; context has changed since the database was created.
- 对于Mybatis在C#.Net中个人使用的总结(一) Mybatis 的结果映射
- zookeeper监控告警
- Dictionary<;实体,List<;实体>;>;的比较
- NET程序的破解--静态分析(Xenocode Fox 2006 Evaluation)
- C++类的常成员函数
- Shuttle ESB 实践
- CAS在Java类中的应用
- Linux 系统化学习系列文章总目录(持续更新中)
- wifi扫描
- mobilebone与weiui_example.css 使用问题
- XUnit测试框架-Python unittest
- Django 的认识,面试题
- 获得最近一天的提交,并使用winscp上传到服务器
- 将Web项目War包部署到Tomcat服务器基本步骤
- 集合框架-ArrayList,Vector,Linkedlist
- 真实分享记录我学习Linux系统遇到的问题