如果有字符位于字符串排序后的位置上就不需要这个字符加入要重排列的字符集合中。最终为了有序这个位置上的字符只能是当前字符或其他位置的相同字符。所以统计排序后不在最终有序位置上的字符即可。
按照排名升序:运动员a的3场比赛优于运动员b时,即a<b,排序后直接检查排名第一的运动员是否严格优于其他选手即可
cf的贪心题解的理解:随意的安排两两链接,此时确定了活动部分和固定部分的交点个数,通过不断松弛,活动部分必加1交点非活动部分和活动部分交点个数不变或加2。简单的说,这个过程交点个数是单调递增的,最终状态为活动部分的弦两两相交。假设这不是交点数量最多的状态,那么活动部分一定不是两两相交的状态。此时一定可以松弛使得情况更优。
于是确定最优状态为活动弦两两相交,在这个基础上计算交点数量即可。
具体而言,这个圆完全可以拆成线,直接抽象成区间相交而不包含的数量总和。连倍增都不需要,两两相交的任一活动弦的左右位置l和r可以表示为i,i+n-k, i
∈
\in
∈[1,n-k]。当然,这个相对位置需要因为固定弦而偏移。标好传送门后。从左到右,以每次遇到的右端点为基准。使用2个树状数组保存扫描过来的左端点和右端点,于是右端点在当前区间内的数量减去左端点在区间内的数量即可得到之前的区间与当前区间相交的次数。这样扫描到结束时间复杂度为
o
(
n
l
o
g
n
)
o(nlogn)
o(nlogn)。