当前位置:网站首页>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
边栏推荐
- Codeforces round 804 (Div. 2) [competition record]
- esxi的安装和使用
- Spark SQL空值Null,NaN判断和处理
- Introduction of motor
- STM32按键消抖——入门状态机思维
- 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]
- Uniapp development, packaged as H5 and deployed to the server
- Curlpost PHP
- Cannot resolve symbol error
- [groovy] compile time meta programming (compile time method interception | method interception in myasttransformation visit method)
猜你喜欢

Folding and sinking sand -- weekly record of ETF

Spark AQE

可恢复保险丝特性测试

STM32 configuration after chip replacement and possible errors

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

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

Introduction of motor
![[groovy] compile time meta programming (AST syntax tree conversion with annotations | define annotations and use groovyasttransformationclass to indicate ast conversion interface | ast conversion inte](/img/61/73becfc3b46669d31b0cf334aa54f2.jpg)
[groovy] compile time meta programming (AST syntax tree conversion with annotations | define annotations and use groovyasttransformationclass to indicate ast conversion interface | ast conversion inte

数据分析思维分析方法和业务知识——分析方法(二)
![Go learning --- structure to map[string]interface{}](/img/e3/59caa3f2ba5bd3647bdbba075ee60d.jpg)
Go learning --- structure to map[string]interface{}
随机推荐
CTF daily question day44 rot
cf:C. The Third Problem【关于排列这件事】
【线上小工具】开发过程中会用到的线上小工具合集
程序员成长第九篇:真实项目中的注意事项
Power query data format conversion, Split Merge extraction, delete duplicates, delete errors, transpose and reverse, perspective and reverse perspective
The value of applet containers
Spark DF adds a column
Lone brave man
多线程与高并发(8)—— 从CountDownLatch总结AQS共享锁(三周年打卡)
小程序技术优势与产业互联网相结合的分析
uniapp开发,打包成H5部署到服务器
STM32 configuration after chip replacement and possible errors
Date类中日期转成指定字符串出现的问题及解决方法
[groovy] JSON serialization (jsonbuilder builder | generates JSON string with root node name | generates JSON string without root node name)
Cloud guide DNS, knowledge popularization and classroom notes
[groovy] XML serialization (use markupbuilder to generate XML data | set XML tag content | set XML tag attributes)
Kotlin core programming - algebraic data types and pattern matching (3)
Notepad++ regular expression replacement string
Classic CTF topic about FTP protocol
如何制作自己的机器人