主页 / 问题 / 1540705
Accepted
Роман
Asked:2023-09-15 02:38:26 +0000 UTC2023-09-15 02:38:26 +0000 UTC

求满足条件后最短时间内的对数

  • 772

任务是找到当 i < j 并且同时 n[i] > n[j] 时对的数量。另外，计数后，第一个出现的数字将成为最后一个。总共有 n - 1 种排列。

示例：输入 0 1 2 3 4

输出：0 4 6 6 4（第一个数字的解释：现在没有对）（第一次排列后我们收到一个数组 1 2 3 4 0 => 我们有 4 对，它们是 1 - 0, 2 - 0 , 3 - 0, 4 - 0) 问题。如何尽可能高效地做到这一点？对于长度为 10^5 的数组。最好在 2 秒内完成。

我的最佳复杂度仅为 O(n^3)。因此，执行时间需要20秒

请告诉我们您使用了什么算法和数据结构

这就是我能做的

n = int(input())
p = list(map(int, input().split()))
sdvig = 0
def changeSdig():
    global  sdvig
    if(sdvig == len(p) - 1):
        sdvig = 0
    else:
        sdvig += 1

def findHappy():
    happy = 0
    for i in range(sdvig, len(p)):
        print(i, end=" ")
        for j in range(i, len(p)):
            print(j, end='')
            if p[i] > p[j]:
                happy += 1
        for j in range(0, sdvig - 1):
            print(j)
            if p[i] > p[j]:
                happy += 1
    #print("---------------------------------")
    for i in range(0, sdvig - 1):
        #print(i, end=" ")
        for j in range(i, sdvig - 1):
            #print(j)
            if p[i] > p[j]:
                happy += 1
    changeSdig()
    print(happy)

findHappy()
for i in range(0, len(p) - 1):
    findHappy()
python

1 个回答

  1. Best Answer

    让我们实现我在类似主题中写的内容

    为了计算反转，我们使用 Fenwick 树（实现方式取自此处，如果范围大于 1..n，则使用排名字典来压缩数据），并修改为沿途为每个索引存储左侧较大的元素，右侧较小的元素的数量。

    经过初步处理后，我们得到了原始数组中的反转次数以及上面的列表。现在，对于每个循环旋转，А我们找到数组各部分之间相互反转的数量K(A)，并应用指定主题中的公式 DeltaInv = A*(N-A) - 2*K(A)

    在 100,000 个元素上花费 0.7 秒。

    import random

def count_inversions(a):
    n = len(a)
    cnt = 0
    smallerright = [0]*n
    largerleft = [0]*n
    res = [0]*n
    rank = {v : i+1 for i, v in enumerate(sorted(a)) }

    counts = [0]*(n+1)
    for j in reversed(range(n)):
        tmpcnt = 0
        x = a[j]
        i = rank[x]-1
        while i:
            cnt += counts[i]
            tmpcnt += counts[i]
            i -= i & -i
        i = rank[x]
        while i <= n:
            counts[i] += 1
            i += i & -i
        smallerright[j] = tmpcnt

    counts = [0]*(n+1)
    for j in range(n):
        tmpcnt = 0
        x = a[j]
        i = rank[x]-1
        while i:
            tmpcnt += counts[i]
            i -= i & -i
        i = rank[x]
        while i <= n:
            counts[i] += 1
            i += i & -i
        largerleft[j] = j - tmpcnt

    res[0] = cnt
    k = 0
    for i in range(1, n):
        k = k  + smallerright[i-1] - largerleft[i-1]
        res[i] = cnt + i*(n-i) - 2 * k

    return res #cnt, smallerright, largerleft



def dumb(a):
    n = len(a)
    res = []
    for i in range(n):
        sh = a[i:] + a[:i]
        ic = 0
        for j in range(n-1):
            for k in range(j+1, n):
                if sh[j]>sh[k]:
                    ic += 1
        res.append(ic)
    return res


n = 6
a = list(range(1, n+1))
random.shuffle(a)

print(a)

print(count_inversions(a))

print(dumb(a))

    结果。底线是使用钝方法进行控制。

    [2, 5, 3, 4, 1, 6]
[6, 9, 6, 7, 6, 11]
[6, 9, 6, 7, 6, 11]
    • 2

相关问题