New Year Chaos

看到这道题目最初使用了冒泡排序的方法，发现在第6-9组测试中出现了超时

def minimumBribes(q):
    time = 0
    for i,v in enumerate(q):
        if (v-1)-i > 2:    
            print("Too chaotic")
            return
    lastIndex =  len(q)-1
    for j in range(0,lastIndex):
        for i in range(0,lastIndex):
            if q[i]>q[i+1]:
                q[i+1],q[i] = q[i],q[i+1]
                time = time+1
    if q ==list(range(1,lastIndex+2)):
        print(str(time))
        return

回头观察发现数据的复杂度达到了10⁵，时间仅仅允许为10秒，而cpu最快能够达到每秒操作1亿次，因此至少需要100秒才能执行完毕，明显超时

之后尝试使用归并排序来计算，当右边先添加到序列中的时候会统计左边还剩下的元素，这一样会出现有时左边的元素出现得过多然后直接移动很多位的情况，此时算法因为没有考虑两位的限制而出错。结果出现小的样本都通过了，大的样本却没有通过的情况

def merge(a,b):
    c = []
    h = j = 0
    global time
    while j < len(a) and h < len(b):
        if a[j] < b[h]:
            c.append(a[j])
            j += 1   
            time = time + (len(a)-j)
            c.append(b[h])
            h += 1
    if j == len(a):
        for i in b[h:]:
            c.append(i)
    else:
        for i in a[j:]:
            c.append(i)
    return c
def merge_sort(lists):
    if len(lists) <= 1:
        return lists
    middle = int(len(lists)/2)
    left = merge_sort(lists[:middle])
    right = merge_sort(lists[middle:])
    return merge(left, right)
def minimumBribes(q):
    global time
    for i,v in enumerate(q):
        if (v-1)-i > 2:    
            print("Too chaotic")
            return
    merge_sort(q)
    print(str(time))
    return

尝试解题失败，以下是对正确答案的观察，令我非常惊奇的是在数据量非常大的情况下python的字典依然正常运行而且没有出现Runtime Error
以下解题的思路是当存在可以交换的项的时候，继续保持大循环的执行，而不是使用外层n的大循环来绑定。导致了循环复杂度不再是n²,这属于什么排序我说不清楚，应该来说，这个算法利用了元素本身并没有过大位移的特征降下了复杂度

b = {}
r = 0
cont = True
while cont:
    cont = False
    for i in range(len(q)-1):
        if q[i] > q[i+1]:
            if not q[i] in b:
                b[q[i]] = 0
            b[q[i]] += 1
            if b[q[i]] > 2:
                cont = False
                r = "Too chaotic"
                break
            print(q)
            q[i], q[i+1] = q[i+1], q[i]
            r += 1
            cont = True

            print(b)
print(r)
#对其结果进行打印观察如下
[1, 2, 5, 3, 7, 8, 6, 4]
{5: 1}
[1, 2, 3, 5, 7, 8, 6, 4]
{5: 1, 8: 1}
[1, 2, 3, 5, 7, 6, 8, 4]
{5: 1, 8: 2}
[1, 2, 3, 5, 7, 6, 4, 8]
{5: 1, 8: 2, 7: 1}
[1, 2, 3, 5, 6, 7, 4, 8]
{5: 1, 8: 2, 7: 2}
[1, 2, 3, 5, 6, 4, 7, 8]
{5: 1, 8: 2, 7: 2, 6: 1}
[1, 2, 3, 5, 4, 6, 7, 8]
{5: 2, 8: 2, 7: 2, 6: 1}
7

python标准答案给出的逻辑就比较难以看懂,而C++的代码就是利用BIT(二叉索引树)的方法来解决，具体二叉索引树是什么来日再研究
区间信息的维护与查询（一）——二叉索引树（Fenwick树、树状数组）

#include <bits/stdc++.h>
using namespace std;

const int maxN=2e5+5;

int n,a[maxN],ans,T,k;
int bit[maxN];
int invalid;

void del() {
    for (k=0;k<maxN;k++) {
        bit[k]=0;        
    }
    ans = 0;
    invalid = 0;
}

void upd(int x) {
    for (k = x; k < maxN; k += (k & (-k))) {
        bit[k]++;
    }
}

int get_sum(int x) {
    int p = 0;
    for (k = x; k > 0; k -= (k & (-k)))
        p += bit[k];
        return p;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        del();
        scanf("%d", &n);

        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
            
        for (int i = n - 1; i >= 0; i--) {
            if (get_sum(a[i]) > 2)
                invalid++;

            ans += get_sum(a[i]);
            upd(a[i]);
        }
        if (invalid > 0) {
            printf("Too chaotic\n");
        } else {
            printf("%d\n", ans);
        }
   }
   return 0;
}

---

Minimum Swaps 2

本题需要找到最少的交换方式，可以知道，在正确的排序下，如果一个元素不在正确的排序的索引位置，那么它正确的索引位置上元素肯定是不正确的。
那么只需要去和这个位置的元素交换，就能够逐步将每个位置排好了
需要注意的点是，在每次交换元素时，相应的索引需要立即交换

def minimumSwaps(arr):
    rightArr = sorted(arr)
    Idx = {v: i for i,v in enumerate(arr)}
    count = 0
    for i,v in enumerate(arr):
        rightNum = rightArr[i]
        if v != rightNum:
            arr[i],arr[Idx[rightNum]] = arr[Idx[rightNum]],arr[i]
            Idx[v],Idx[rightNum] = Idx[rightNum],Idx[v]
            count = count + 1
    return count