当前位置:网站首页>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
边栏推荐
- 图解网络:TCP三次握手背后的原理,为啥两次握手不可以?
- RAID disk redundancy queue
- cf:C. The Third Problem【关于排列这件事】
- 【EI会议分享】2022年第三届智能制造与自动化前沿国际会议(CFIMA 2022)
- Problems and solutions of converting date into specified string in date class
- Synchronized and reentrantlock
- MDK debug时设置数据实时更新
- synchronized 和 ReentrantLock
- 【文件IO的简单实现】
- STM32 key chattering elimination - entry state machine thinking
猜你喜欢
Spark AQE
关于#数据库#的问题:(5)查询库存表中每本书的条码、位置和借阅的读者编号
For a deadline, the IT fellow graduated from Tsinghua suddenly died on the toilet
Model analysis of establishment time and holding time
Go learning - dependency injection
时间戳的拓展及应用实例
图解网络:TCP三次握手背后的原理,为啥两次握手不可以?
MYSQL GROUP_ The concat function realizes the content merging of the same ID
Opencv classic 100 questions
SAP Spartacus home 页面读取 product 数据的请求的 population 逻辑
随机推荐
Study diary: February 13, 2022
Intensive learning weekly, issue 52: depth cuprl, distspectrl & double deep q-network
The relationship between FPGA internal hardware structure and code
Leetcode Fibonacci sequence
Model analysis of establishment time and holding time
RAID disk redundancy queue
Yolov5, pychar, Anaconda environment installation
anconda下载+添加清华+tensorflow 安装+No module named ‘tensorflow‘+KernelRestarter: restart failed,内核重启失败
看抖音直播Beyond演唱会有感
Introduction of motor
Classical concurrency problem: the dining problem of philosophers
Set data real-time update during MDK debug
Arduino六足机器人
电机的简介
Folding and sinking sand -- weekly record of ETF
Reading notes of the beauty of programming
[Chongqing Guangdong education] Chongqing Engineering Vocational and Technical College
notepad++正則錶達式替換字符串
DD's command
《强化学习周刊》第52期:Depth-CUPRL、DistSPECTRL & Double Deep Q-Network