好久不写题了,写个试试。这个算Mathematica里吧,要不东西太少了。
题目:http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1185
大概是说,给你一个数组,求这个数组的逆序数。
求逆序数的暴力方法:对于输入a[i]求a[1]…a[i-1]中大于于a[i]的数的个数,然后对所有这样的数求和。因而是o(n^2)。
正常解法:首先想到排序,之后自然想到归并排序。考虑到归并排序中要对两个排列好的子串依次送入结果串,并且可以根据目前子串位置决定后面子串在前面子串的排名,因此可以得到逆序数。
对于任意两个子串,后面子串中的数的位置不影响其对于前面子串的逆序数。而任意一个数的逆序数由在本子串的逆序数与对于前子串的逆序数的和。因此可以将两个子串排序,根据后面子串中数在前面子串中的插入位置决定其在前面子串的逆序数。对于本子串的逆序数由递归求得。
代码:
点击获取源文件
19 replies on “[切菜题][boj1185]归并排序”
你可爱的被无辜的browser当作亲人藏了起来~~~
求解释。。。
失算了。。。应该是 & l t ;
我把代码给咔嚓了。。。
这个还要想另外的办法。。。
en,如果你不是hardcode的话应该没问题的~~
要考试了,考前焦虑……
我也焦虑,感觉有好多事没做。
还有一个月期末考试,我什么都不会。疯了疯了。
什么都不会得考完了一门,明天还有一天的天地考……我突然意识到我生命力很顽强……
RSS提示回复吗?
恩,看经济去了……
The more you want to do, the more you haven’t done; The more you haven’t done, the less you have; then, why do them?
我想做邮件提醒,增加个checkbox,选择是否提醒,RSS还不是很普及。。。
又要我好多邮件了……我把你的RSS弄进gmail了哦哈哈~~今早考试木有带笔,木有带笔,带笔,笔。。。
哦。。。你够牛了,考试不带笔。老土的老师会用一个很蹩脚的比喻跟你说,考试不带笔,就像上战场不带枪。其实我觉得这个没有可比性,战场你可以缴获,考试你不可以抢别人的。邮件那个设置为可选,这样比较人性一点。
我倒是很想抢别人的……嗯……
我应该去申请个短点的邮箱地址——每次都打邮箱好长啊……
要不我给你整个帐号?然后保存你的信息,这样你回复的话就可以只打内容了。
So many thx~!! 发现你变体贴了哦哈哈~~
小bug一枚——我回复了14楼以后页面上方还写着13 comments
我发现我越来越挑剔了其实也……
哈,我就知道你会发现它的。这就是Ajax讨厌的地方,如果页面内容关联强的化,更新的时候一不小心就会漏掉该更新的地方。
等给你弄帐号的时候再修正bug好了。
虽然无关紧要,其实也无关紧要,嘿嘿:-)
突然想问,这是你博客里回复最多的东东吗?
这个有可能。