mipha


私信TA

用户名:dotcpp0664923

访问量:857

签 名:

如果插,请深插

等  级
排  名 24685
经  验 547
参赛次数 0
文章发表 2
年  龄 0
在职情况 学生
学  校
专  业

  自我简介:

TA的其他文章

解题思路:

        首先题目描述有问题,没有说明 i 和 j 的关系,应该是保证 i < j 时使  Ai > Aj (简称逆序对) ,我不太理解,这可是比赛,描述竟然能如此含糊,爷想笑,水份杯果然名不虚传。

        思路如下:

        ① 优先考虑特殊情况,数组是一个严格递减的数组(每个数字之间相差1,最后一位必须为1),例子如下:

                长度为 7 ,对应的数组为 [7,6,5,4,3,2,1],根据组合数学 C(7 , 2) = 21,共有21对逆序对

                长度为 8 ,对应的数组为 [8,7,6,5,4,3,2,1],根据组合数学 C(8 , 2) = 28,共有28对逆序对

            假设逆序对个数为 x 时,当 x ∈ (21,28] ,其数组长度为 8;当 x = 21 时,数组长度为 7

            如何去求数组长度呢?假设 数组 长度为 L ,C(L , 2) ≥ x,可以二分长度,也可以直接解方程,简简单单二元一次方程,初中知识:

                            L * (L-1) / 2 ≥ x

                    =>   L2 - L - 2x  ≥ 0

            然后套求根公式,求出正根即可,当 C(L , 2) 刚好等于 x,那答案就是一个严格递减的数组 (每个数字之间相差1,最后一位必须为1)


        ② 那么如果 C(L , 2) 不等于 x 呢,假如 x = 25,通过第①步可以求得 L = 7,数组为  [7,6,5,4,3,2,1] ,共 21 对逆序对,那么差4对怎么补齐?其实只要在数组开头添加一个 5 即可,数组变为 [5,7,6,5,4,3,2,1],多了第一个5和黄色的数字组成的逆序对,刚好4对

            当然这个只是其中一个答案,不符合字典序最小的要求。因此需要化简:

                  一、   [5,7,6,5,4,3,2,1] 把5改成4 得到 [5,7,6,4,4,3,2,1] ,可以发现逆序对的个数是没有变化的,那是因为原来加粗了的逆序对,改变成了修改后加粗的逆序对,也仅有这一对发生了转移,因此逆序对个数没变,但是字典序变小了。

                  

                  二、 [5,7,6,4,4,3,2,1]  贪心,把黄色部分都减1 得到 [5,6,5,4,4,3,2,1],很明显逆序对个数依然没有改变,但是字典序变小了。

                   

                  三、[5,6,5,4,4,3,2,1] 黄色部分改成 [5,6,5,4,3,2,1,1] ,相当于把 4 变成 1 ,可以发现逆序对个数依然没有改变,但是字典序变小了。

                    

                  四、[5,6,5,4,3,2,1,1] 这情况又和第一步很相似了,把5改成4 得到 [5,6,4,4,3,2,1,1],一直重复步骤一至步骤三,可以得到最终结果:

                                                            [5,4,3,3,2,2,1,1]

                          这个结果就是最"简化"了的,也就是字典序最小

        

        ③ 找规律 x ∈ (21,28] ,结果如下:

                

2226543211
23
35432211
24
44332211
25
54332211
26
65432211
27
76543211
28
87654321

                根据标黄标红的部分可以发现有很明显的规律,就像两个三角形,或者阶梯更恰当。

                黄色阶梯没有标黄的部分,规律都是严格递减的

                红色阶梯没有标红的部分,除了开头那个数字,规律都是严格递减的,而开头的数字跟加粗的数字是相等的

                

                有这些规律就足够得出结果了。





参考代码 (python):

n = int(input())


# x*(x-1)/2 >= n

# x2 - x - 2*n >= 0

# 求根公式获取结果数组长度

x = int((1 + (1+8*n)**0.5) / 2)

if x*(x-1) == 2 * n:

    print(x)

    print(x,end='')

    x -= 1

    while x:

        print(' ',end='')

        print(x,end='')

        x -= 1

else:

    x += 1

    print(x)

    total = x*(x-1)//2

    # 倒数第total个

    total -= n

    from collections import deque

    

    res = deque()

    

    # 黄色阶梯部分

    if total <= x // 2:

        num = 1

        while num <= total:

            res.append(num)

            res.append(num)

            num += 1

        while len(res) < x:

            res.append(num)

            num += 1

    # 红色阶梯部分

    else:

        tmp = x - total - 1

        num = 1

        while num <= tmp:

            res.append(num)

            res.append(num)

            num += 1

        tmp = num

        while len(res) < x - 1:

            res.append(num)

            num += 1

        res.append(tmp)

    

    

    print(res.pop(),end='')

    while res:

        print(' ',end='')

        print(res.pop(),end='')

print()


 

0.0分

9 人评分

  评论区

666
2024-03-10 14:52:37
  • «
  • 1
  • »