Reduce inversion count 求最小逆序数
本问题出自:微软2014实习生及秋令营技术类职位在线测试 (Microsoft Online Test for Core Technical Positions)
Description
Find a pair in an integer array that swapping them would maximally decrease the inversion count of the array. If such a pair exists, return the new inversion count; otherwise returns the original inversion count.
在一个数列中选择两个数,交换他们的顺序使得逆序数变得最小,给出这个逆序数值。
Definition of Inversion: Let (A[0], A[1] ... A[n], n <= 50) be a sequence of n numbers. If i < j and A[i] > A[j], then the pair (i, j) is called inversion of A.
定义:在数列A[n]中,如果i < j 且A[i] > A[j],那么(i, j)就是A的一个逆序。
Example:
Count(Inversion({3, 1, 2})) = Count({3, 1}, {3, 2}) = 2
InversionCountOfSwap({3, 1, 2})=>
{
InversionCount({1, 3, 2}) = 1 <-- swapping 1 with 3, decreases inversion count by 1
InversionCount({2, 1, 3}) = 1 <-- swapping 2 with 3, decreases inversion count by 1
InversionCount({3, 2, 1}) = 3 <-- swapping 1 with 2 , increases inversion count by 1
}
Input
Input consists of multiple cases, one case per line.Each case consists of a sequence of integers separated by comma.
Output
For each case, print exactly one line with the new inversion count or the original inversion count if it cannot be reduced.
Sample Input
3,1,2
1,2,3,4,5
Sample Output
1
0
解题思路
对于一个数列,首先求出其逆序数。
如果逆序数不等于0(不是顺序排列),那么一定有可以减小的方法(在一个排列中对换相邻的元素,如果把小的换到大的之前,那么逆序数减一)
一种做法是:
遍历所有的数对,对比这两个数和他们之间的数,由“在一个排列中对换相邻的元素,如果把小的换到大的之前,那么逆序数减一,反之加一”计算出减少的逆序数,选择减少最多的。
最新文章
- airflow 部署
- Windows中遇到的些问题及解决办法
- js原型基础
- JS获取节点的兄弟,父级,子级元素的方法(js获取子级获取到换行与空格元素-FF)
- js中的什么时候需要用new来实例化?
- Ubuntu修改hosts方法
- Cocos2d 初学基本知识
- Android 自定义TimePickerDialog
- java笔试题(4)
- CodeForces 489A (瞎搞) SwapSort
- Codevs 1173 最优贸易 2009年NOIP全国联赛提高组
- C#正则表达式之字符替换
- 南京Uber优步司机奖励政策(2月1日~2月7日)
- VirtualBox中的Ubuntu没有权限访问共享文件夹/media/sf_bak
- js快速分享代码
- Android SQLite 数据库 增删改查操作
- 怎么让猫吃辣椒 转载自 xiaotie
- JavaScript中的事件模型
- EF Core Model更新迁移
- 2845 ACM 豆子 beans