当前位置:网站首页>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】

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
边栏推荐
猜你喜欢
![[groovy] compile time metaprogramming (compile time method injection | method injection using buildfromspec, buildfromstring, buildfromcode)](/img/e4/a41fe26efe389351780b322917d721.jpg)
[groovy] compile time metaprogramming (compile time method injection | method injection using buildfromspec, buildfromstring, buildfromcode)

Go learning - dependency injection

OpenCV经典100题

从 1.5 开始搭建一个微服务框架——调用链追踪 traceId

Idea remotely submits spark tasks to the yarn cluster

Data analysis thinking analysis methods and business knowledge - analysis methods (III)

猿桌派第三季开播在即,打开出海浪潮下的开发者新视野

LeetCode 1189. Maximum number of "balloons"

Intensive learning weekly, issue 52: depth cuprl, distspectrl & double deep q-network

cf:D. Insert a Progression【关于数组中的插入 + 绝对值的性质 + 贪心一头一尾最值】
随机推荐
vSphere实现虚拟机迁移
Natural language processing (NLP) - third party Library (Toolkit):allenlp [library for building various NLP models; based on pytorch]
China Taiwan strategy - Chapter 8: digital marketing assisted by China Taiwan
devkit入门
Cannot resolve symbol error
How to use the flutter framework to develop and run small programs
Power Query数据格式的转换、拆分合并提取、删除重复项、删除错误、转置与反转、透视和逆透视
Yolov5、Pycharm、Anaconda环境安装
Go learning - dependency injection
I'm interested in watching Tiktok live beyond concert
Calculate sha256 value of data or file based on crypto++
STM32 key chattering elimination - entry state machine thinking
【线上小工具】开发过程中会用到的线上小工具合集
云导DNS和知识科普以及课堂笔记
KDD 2022 | EEG AI helps diagnose epilepsy
Intranet Security Learning (V) -- domain horizontal: SPN & RDP & Cobalt strike
The third season of ape table school is about to launch, opening a new vision for developers under the wave of going to sea
Pointer - character pointer
Room cannot create an SQLite connection to verify the queries
NLP basic task word segmentation third party Library: ICTCLAS [the third party library with the highest accuracy of Chinese word segmentation] [Chinese Academy of Sciences] [charge]