专栏首页WD学习记录牛客网 数列还原

牛客网 数列还原

题目:数列还原

题目描述

牛牛的作业薄上有一个长度为 n 的排列 A,这个排列包含了从1到n的n个数,但是因为一些原因,其中有一些位置(不超过 10 个)看不清了,但是牛牛记得这个数列顺序对的数量是 k,顺序对是指满足 i < j 且 A[i] < A[j] 的对数,请帮助牛牛计算出,符合这个要求的合法排列的数目。

输入描述:

每个输入包含一个测试用例。每个测试用例的第一行包含两个整数 n 和 k(1 <= n <= 100, 0 <= k <= 1000000000),接下来的 1 行,包含 n 个数字表示排列 A,其中等于0的项表示看不清的位置(不超过 10 个)。

输出描述:

输出一行表示合法的排列数目。

示例1

输入

5 5
4 0 0 2 0

输出

2

解答:

自己的方法:直接全排列,然后计算每个的顺序对数目,提交通过。

n,k=[int(each) for each in input().split()]
arrs=[int(each) for each in input().split()]
unused_arr=[i for i in range(1,n+1)]
for i in arrs:
    if i in unused_arr:
        unused_arr.remove(i)

import itertools
unused_arr_ordered=[]
for i in itertools.permutations(unused_arr):
    unused_arr_ordered.append(i)


def getOrderedPairs(arrs):
    tmp_c=0
    for i in range(n):
        for j in range(i,n):
            if arrs[i]<arrs[j]:
                tmp_c+=1
    return tmp_c

count=0
for unused_arr_tmp in unused_arr_ordered:
    tmp_arrs=[ele for ele in arrs]
    for i in unused_arr_tmp:
        tmp_index=tmp_arrs.index(0)
        tmp_arrs[tmp_index]=i
    if getOrderedPairs(tmp_arrs)==k:
        count+=1

print(count)

参考解法:数列还原

这种解法的解析参考代码中的注释,整体思路为,原始数组中的顺序对数+剩余数字产生的顺序对数+数字在每个位置的顺序对数

# 获取没有在输入数组中的数组,并且进行全排列,并且每个全排列内的顺序对数
# 给出例子中为:[([1, 3, 5], 3), ([1, 5, 3], 2), ([3, 1, 5], 2), ([3, 5, 1], 1), ([5, 1, 3], 1), ([5, 3, 1], 0)]
def gothrough(result, picked, rest):
    if len(rest) == 0:
        count = 0
        for i in range(len(picked)):
            for j in range(i + 1, len(picked)):
                if picked[i] < picked[j]:
                    count += 1
        result.append((picked, count))
        return
    else:
        for each in rest:
            nextpick = picked + [each]
            nextrest = rest - {each}
            gothrough(result, nextpick, nextrest)
        return


n, kk = [int(each) for each in input().split()]
d = [int(each) for each in input().split()]
# 获取不在d中的数字
loss = list(set([i for i in range(1, n + 1)]) - set(d))
# print(loss)

# 获取d中为0的位置数目
loss_p = []
for i in range(n):
    if d[i] == 0:
        loss_p.append(i)
# print(loss_p)

# d中原始的顺序对数
settlecount = 0
for i in range(n - 1):
    if d[i] != 0:
        for j in range(i + 1, n):
            if d[i] < d[j]:
                settlecount += 1
# print(settlecount)

# 缺失的数字在每个对应位置时的顺序对数
# 给出例子的结果为:{1: [1, 1, 0], 3: [0, 0, 1], 5: [1, 1, 2]}
countonposition = {}
# [[0 for i in range(len(loss_p))] for j in range(len(loss))]
for i in range(len(loss)):
    count = 0
    k = 0
    countonposition[loss[i]] = [0 for _ in range(len(loss_p))]
    # 先从前到后
    for j in range(n):
        if d[j] != 0:
            if d[j] < loss[i]:
                count += 1
        else:
            countonposition[loss[i]][k] = count
            k += 1
            if k == len(loss_p):
                break
    count = 0
    k = len(loss_p) - 1
    # 再从后向前遍历
    for j in range(n - 1, -1, -1):
        if d[j] != 0:
            if d[j] > loss[i]:
                count += 1
        else:
            countonposition[loss[i]][k] += count
            k -= 1
            if k == -1:
                break
# print(countonposition)

self_result = []
gothrough(self_result, [], set(loss))
# print(self_result)

possible = 0
for picked, count in self_result:
    # print(picked, count)
    # 每种全排列本身的顺序对数,加上每个数字在对应位置产生的新的顺序对数
    for i in range(len(picked)):
        count += countonposition[picked[i]][i]
    # 再加上原始d中的顺序对数
    count += settlecount
    if count == kk:
        possible += 1
        # print(picked)

print(possible)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 牛客网 跳石板

    小易来到了一条石板路前,每块石板上从1挨着编号为:1、2、3....... 这条石板路要根据特殊的规则才能前进:对于小易当前所在的编号为K的 石板,小易单次只...

  • 每周一总结(4) 分布式ID 学习笔记

    趋势递增:分布式ID用来标识数据的唯一性,往往会被用作主键或者是唯一索引。常用的MySQL InnoDB,使用的索引往往是BTree索引,自增的数据在插入时会有...

  • 8-18 Android学习ing

    getSharedPreferences("1234", Context.MODE_PRIVATE)  之中的名字不能带有后缀名,比如1234.xml

  • python中的推导式

    首先看 for i in range(10):当 i 依次取 range(10) (0,1,2,3,4,5,6,7,8,9)时

    阿黎逸阳
  • python之打印九九乘法表

    py3study
  • Python练手例子(11)

    py3study
  • Python学习没有捷径,但可以加速,零基础九天你也可以会编程

    在小学生都学Python了,你还不知道怎么开始文中介绍了Python的应用广泛,功能强大,提供了Python的在线学习视频和资料等 (收集资料是我们的最爱)。...

    生信宝典
  • python 编程实例 1

    #题目:有 1、2、3、4 个数字,能组成多少个互不相同且无重复数字的三位数?都是多 

    py3study
  • 18.Python中的for...range循环

    Python的for循环很灵活,可以实现很多定制的功能。可以使用for循环进行遍历的对象被称为可迭代对象,序列就是一种可迭代对象。 迭代(遍历)特定范围的数值...

    用户4381798
  • python中for in的用法详解

    到此这篇关于python中for in的用法详解的文章就介绍到这了,更多相关python for in内容请搜索ZaLou.Cn

    砸漏

扫码关注云+社区

领取腾讯云代金券