09201: Freda的越野跑

http://cs101.openjudge.cn/practice/09201/

Freda报名参加了学校的越野跑。越野跑共有N人参加，在一条笔直的道路上进行。这N个人在起点处站成一列，相邻两个人之间保持一定的间距。比赛开始后，这N个人同时沿着道路向相同的方向跑去。换句话说，这N个人可以看作x轴上的N个点，在比赛开始后，它们同时向x轴正方向移动。假设越野跑的距离足够远，这N个人的速度各不相同且保持匀速运动，那么会有多少对参赛者之间发生“赶超”的事件呢？

输入

第一行1个整数N。第二行为N 个非负整数，按从前到后的顺序给出每个人的跑步速度。对于50%的数据，2<=N<=1000。对于100%的数据，2<=N<=100000。

输出

一个整数，表示有多少对参赛者之间发生赶超事件。

样例输入

5
1 3 10 8 5

样例输出

提示

我们把这5个人依次编号为A,B,C,D,E，速度分别为1,3,10,8,5。在跑步过程中： B,C,D,E均会超过A，因为他们的速度都比A快； C,D,E都会超过B，因为他们的速度都比B快； C,D,E之间不会发生赶超，因为速度快的起跑时就在前边。

python

import sys

def merge_sort(a, temp, left, right):
    if right - left <= 1:
        return 0
    mid = (left + right) // 2
    inv_count = merge_sort(a, temp, left, mid) + merge_sort(a, temp, mid, right)
    i, j, k = left, mid, left
    while i < mid and j < right:
        if a[i] < a[j]:
            temp[k] = a[i]
            i += 1
        else:
            temp[k] = a[j]
            j += 1
            inv_count += mid - 
            
        k += 1
    while i < mid:
        temp[k] = a[i]
        i += 1
        k += 1
    while j < right:
        temp[k] = a[j]
        j += 1
        k += 1
    for i in range(left, right):
        a[i] = temp[i]
    return inv_count

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
temp = [0] * n
print(n * (n - 1) // 2 - merge_sort(a, temp, 0, n))

python

#蒋子轩
from bisect import *
n=int(input())
a=list(map(int,input().split()))
sorted_list=[]
cnt=0
for num in a:
    pos=bisect_left(sorted_list,num)
    cnt+=pos
    insort_left(sorted_list,num)
print(cnt)

python

# 23物院宋昕杰 树状数组
n = int(input())
tr = [0] * (n + 1)


def lowbit(x):
    return x & -x


def query(x, y):  			#查询[x, y]，索引从1开始
    x -= 1
    ans = 0
    while y > x:
        ans += tr[y]
        y -= lowbit(y)
    while x > y:
        ans -= tr[x]
        x -= lowbit(x)
    return ans


def add(i, k):				#原数组第i个数加上k，更新树状数组
    while i <= n:
        tr[i] += k
        i += lowbit(i)


ls = list(map(int, input().split()))
for i in range(1, n + 1):		#O(nlogn)建树
    add(i, 1)
keys = sorted(ls)
dic = {}
for i in range(n):
    if keys[i] not in dic:
        dic[keys[i]] = i
ans = 0
for i in range(n - 1, -1, -1):
    idx = dic[ls[i]]
    ans += query(1, idx)
    add(idx + 1, -1)
print(ans)

09201: Freda的越野跑 ​

09201: Freda的越野跑