当前位置:网站首页>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
边栏推荐
- MCU通过UART实现OTA在线升级流程
- 详细页返回列表保留原来滚动条所在位置
- Opencv classic 100 questions
- 小程序技术优势与产业互联网相结合的分析
- Introduction of motor
- Date类中日期转成指定字符串出现的问题及解决方法
- Intensive learning weekly, issue 52: depth cuprl, distspectrl & double deep q-network
- 数据分析思维分析方法和业务知识——分析方法(三)
- Location based mobile terminal network video exploration app system documents + foreign language translation and original text + guidance records (8 weeks) + PPT + review + project source code
- Getting started with devkit
猜你喜欢

MySQL存储引擎

cf:C. The Third Problem【关于排列这件事】

Leetcode 450 deleting nodes in a binary search tree

How to solve the problems caused by the import process of ecology9.0

uniapp开发,打包成H5部署到服务器

Anconda download + add Tsinghua +tensorflow installation +no module named 'tensorflow' +kernelrestart: restart failed, kernel restart failed

Cannot resolve symbol error

Free chat robot API

看抖音直播Beyond演唱会有感

Spark AQE
随机推荐
Getting started with devkit
FFmpeg抓取RTSP图像进行图像分析
How to solve the problems caused by the import process of ecology9.0
Atcoder beginer contest 254 [VP record]
CTF daily question day44 rot
Introduction of motor
The third season of ape table school is about to launch, opening a new vision for developers under the wave of going to sea
Single source shortest path exercise (I)
DD's command
《强化学习周刊》第52期:Depth-CUPRL、DistSPECTRL & Double Deep Q-Network
Analysis of the combination of small program technology advantages and industrial Internet
Go learning --- structure to map[string]interface{}
Spark SQL空值Null,NaN判断和处理
Solve the problem of reading Chinese garbled code in sqlserver connection database
vSphere实现虚拟机迁移
NLP generation model 2017: Why are those in transformer
Arduino六足机器人
【线上小工具】开发过程中会用到的线上小工具合集
Set data real-time update during MDK debug
Room cannot create an SQLite connection to verify the queries