当前位置:网站首页>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
边栏推荐
- An understanding of & array names
- Meta AI西雅图研究负责人Luke Zettlemoyer | 万亿参数后,大模型会持续增长吗?
- Classical concurrency problem: the dining problem of philosophers
- Novice entry depth learning | 3-6: optimizer optimizers
- STM32按键消抖——入门状态机思维
- DD's command
- Free chat robot API
- Promise
- Spark SQL UDF function
- [Chongqing Guangdong education] Chongqing Engineering Vocational and Technical College
猜你喜欢

小程序技术优势与产业互联网相结合的分析

notepad++正则表达式替换字符串

MCU通过UART实现OTA在线升级流程

Go learning - dependency injection

Set data real-time update during MDK debug

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

Browser reflow and redraw

Analysis of the combination of small program technology advantages and industrial Internet

FFmpeg抓取RTSP图像进行图像分析

《强化学习周刊》第52期:Depth-CUPRL、DistSPECTRL & Double Deep Q-Network
随机推荐
Power query data format conversion, Split Merge extraction, delete duplicates, delete errors, transpose and reverse, perspective and reverse perspective
Extension and application of timestamp
cf:D. Insert a Progression【关于数组中的插入 + 绝对值的性质 + 贪心一头一尾最值】
XML Configuration File
An understanding of & array names
Getting started with devkit
Folding and sinking sand -- weekly record of ETF
常用API类及异常体系
Kotlin core programming - algebraic data types and pattern matching (3)
FFmpeg抓取RTSP图像进行图像分析
Single source shortest path exercise (I)
Novice entry depth learning | 3-6: optimizer optimizers
Spark DF增加一列
logstash清除sincedb_path上传记录,重传日志数据
Spark SQL空值Null,NaN判断和处理
Anconda download + add Tsinghua +tensorflow installation +no module named 'tensorflow' +kernelrestart: restart failed, kernel restart failed
NLP text processing: lemma [English] [put the deformation of various types of words into one form] [wet- > go; are- > be]
Model analysis of establishment time and holding time
[groovy] compile time meta programming (AST syntax tree conversion with annotations | define annotations and use groovyasttransformationclass to indicate ast conversion interface | ast conversion inte
Classic CTF topic about FTP protocol