当前位置:网站首页>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
边栏推荐
- Leetcode:20220213 week race (less bugs, top 10% 555)
- Kotlin core programming - algebraic data types and pattern matching (3)
- Keepalive component cache does not take effect
- Starting from 1.5, build a micro Service Framework - call chain tracking traceid
- Spark AQE
- Spark-SQL UDF函数
- How to solve the problems caused by the import process of ecology9.0
- [Chongqing Guangdong education] reference materials for Zhengzhou Vocational College of finance, taxation and finance to play around the E-era
- CTF daily question day44 rot
- How to use the flutter framework to develop and run small programs
猜你喜欢
可恢复保险丝特性测试
Intranet Security Learning (V) -- domain horizontal: SPN & RDP & Cobalt strike
建立时间和保持时间的模型分析
[groovy] XML serialization (use markupbuilder to generate XML data | create sub tags under tag closures | use markupbuilderhelper to add XML comments)
I'm interested in watching Tiktok live beyond concert
Anconda download + add Tsinghua +tensorflow installation +no module named 'tensorflow' +kernelrestart: restart failed, kernel restart failed
数据分析思维分析方法和业务知识——分析方法(三)
MCU realizes OTA online upgrade process through UART
Keepalive component cache does not take effect
MDK debug时设置数据实时更新
随机推荐
Set data real-time update during MDK debug
KDD 2022 | EEG AI helps diagnose epilepsy
Power Query数据格式的转换、拆分合并提取、删除重复项、删除错误、转置与反转、透视和逆透视
[groovy] compile time meta programming (AST syntax tree conversion with annotations | define annotations and use groovyasttransformationclass to indicate ast conversion interface | ast conversion inte
MySQL storage engine
常用API类及异常体系
Notepad + + regular expression replace String
MYSQL GROUP_ The concat function realizes the content merging of the same ID
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
[EI conference sharing] the Third International Conference on intelligent manufacturing and automation frontier in 2022 (cfima 2022)
Leetcode Fibonacci sequence
FPGA内部硬件结构与代码的关系
数据分析思维分析方法和业务知识——分析方法(二)
DD's command
新手入门深度学习 | 3-6:优化器optimizers
Idea remotely submits spark tasks to the yarn cluster
Kotlin core programming - algebraic data types and pattern matching (3)
Date类中日期转成指定字符串出现的问题及解决方法
Lone brave man
Ffmpeg captures RTSP images for image analysis