「LibreOJ Round
虽然写几个不同的方法写了三个小时,做这道题收获还是挺大/cy.
题目
\(n\)个烟火排成一排，从左到右高度分别为\(h-1,h-2,...,h-n\)
，这些高度两两不同。
每次 Yoko 可以选择两个相邻的烟火交换，这样的交换可以进行任意多次。 每次
Yoko 还可以选择两个不相邻的烟火交换，但这样的交换至多进行一次。
你的任务是帮助 Yoko 用最少次数的交换，使这些烟火从左到右的高度递增。
题解
0分
这个就各显神通了.
17分
好像也没什么好说的,直接暴搜就可以了.
41分
其实对于交换不相邻的烟火,先后顺序是无所谓的.
因为即使最开始不交换,也可以按照交换了的情况去操作,最后再交换.这样次数也是一样的.
那么就不妨最开始就进行交换不相邻元素的操作.
之后剩下的都只能交换相邻的,交换次数就是逆序对的个数.
因为所有元素排好序也等价于没有逆序对,每一次交换就会减少一个逆序对,所以逆序对个数也就是剩下的交换次数了.
code
实际上也不用每次都去重新算逆序对,可以考虑交换元素之后的变化,这样做能多过一个子任务,不过太麻烦了.
67分
可以想到数形结合,这也是后面做法的基础.
在以序号为横轴,权值为纵轴的平面直角坐标系上,每个点的逆序对就是它左上方的元素.
第一步交换两个不相邻的点减少的逆序对数等于左上方的点和右下方的点构成的矩形中包含的点的个数.(不包括这两个点本身).
随便画个图模拟一下就很好理解.
一个直观的想法就是二维前缀和.就可以\(/mathjaxcal{O}(1)\)算出来交换两个点后还需要的交换次数.
code
100分
有了前面的基础这个应该不难理解.
直观的想法是用线段数加扫描线的方法去数点.但是这个太难写了先鸽了
\(67\)分的做法主要慢在算矩形中的点上.
选的两个点决策是满足单调性的,而且分别在两个从\(1\)开始和到\(n\)结束的上升子序列上面.
然后分治就行了.
可以用树状数组来快速算出某个矩形中的点数,好像都是基本操作?
code
有时间写一下另一个做法...