当前位置:网站首页>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
边栏推荐
- 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]
- Classic CTF topic about FTP protocol
- 图解网络:TCP三次握手背后的原理,为啥两次握手不可以?
- Atcoder beginer contest 258 [competition record]
- Pointer pointer array, array pointer
- C language programming (Chapter 6 functions)
- 常用API类及异常体系
- Leetcode Fibonacci sequence
- [groovy] compile time metaprogramming (compile time method injection | method injection using buildfromspec, buildfromstring, buildfromcode)
- Opencv classic 100 questions
猜你喜欢

《强化学习周刊》第52期:Depth-CUPRL、DistSPECTRL & Double Deep Q-Network
![Go learning --- structure to map[string]interface{}](/img/e3/59caa3f2ba5bd3647bdbba075ee60d.jpg)
Go learning --- structure to map[string]interface{}
![[groovy] JSON serialization (convert class objects to JSON strings | convert using jsonbuilder | convert using jsonoutput | format JSON strings for output)](/img/52/021931181ad3f4bef271b4e98105c2.jpg)
[groovy] JSON serialization (convert class objects to JSON strings | convert using jsonbuilder | convert using jsonoutput | format JSON strings for output)

Spark SQL空值Null,NaN判断和处理

常用API类及异常体系

KDD 2022 | EEG AI helps diagnose epilepsy

图解网络:TCP三次握手背后的原理,为啥两次握手不可以?

I'm interested in watching Tiktok live beyond concert

STM32 configuration after chip replacement and possible errors

Notepad++ regular expression replacement string
随机推荐
The detailed page returns to the list and retains the original position of the scroll bar
DD's command
Opencv classic 100 questions
Yolov5, pychar, Anaconda environment installation
I'm interested in watching Tiktok live beyond concert
Intensive learning weekly, issue 52: depth cuprl, distspectrl & double deep q-network
Set data real-time update during MDK debug
[groovy] JSON serialization (jsonbuilder builder | generates JSON string with root node name | generates JSON string without root node name)
Anconda download + add Tsinghua +tensorflow installation +no module named 'tensorflow' +kernelrestart: restart failed, kernel restart failed
Uniapp development, packaged as H5 and deployed to the server
Solve the problem of reading Chinese garbled code in sqlserver connection database
Spark DF增加一列
如何制作自己的機器人
Problems and solutions of converting date into specified string in date class
Spark-SQL UDF函数
Pointer - character pointer
Pointer pointer array, array pointer
Spark AQE
Cloud guide DNS, knowledge popularization and classroom notes
A preliminary study of geojson