当前位置:网站首页>Cf:d. insert a progression [about the insert in the array + the nature of absolute value + greedy top-down]

Cf:d. insert a progression [about the insert in the array + the nature of absolute value + greedy top-down]

2022-07-06 00:44:00 White speed Dragon King's review

 Insert picture description here

analysis

Please see the notes for explanation
consider 1 and x
Three situations are sufficient

ac code

import sys
input = sys.stdin.readline

# we want to insert x into a1 ... an
# if x belongs to [a1, an]
# there must be a period s.t. ai <= x <= aj
# which means the extra effect of x disappear
# therefore we only need to consider 1 and x
# others can insert between 1 and x, just vaporate

# if min <= 1 and x <= max nothing happen
# otherwise, we consider 1 < min
# three cases: abs(1 - a.front()), abs(1 - a.back()), abs(1 - min) * 2
# e.g. minn 1 ai, 1 give extra 2 * (minn - 1)

for _ in range(int(input())):
    n, x = list(map(int, input().split()))
    a = list(map(int, input().split()))
    ans = 0
    for i in range(1, n):
        ans += abs(a[i] - a[i - 1])

    # for 1 <= min
    p = min(abs(1 - a[0]), abs(1 - a[-1]), 2 * abs(1 - min(a)))
    # for x
    q = 0
    if x > max(a):
        q = min(abs(x - a[0]), abs(x - a[-1]), 2 * abs(x - max(a)))
    ans += p + q
    print(ans)

summary

The nature of absolute value is interesting

原网站

版权声明
本文为[White speed Dragon King's review]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/187/202207060036450849.html