#214. 加勒比海的猪兄弟Ⅱ——鬼影幢幢!亡灵岛的暗影城堡

    ID: 214 Type: Default 1000ms 256MiB Tried: 5 Accepted: 1 Difficulty: 10 Uploaded By: Tags>CodeForces2025寒假一期结训赛

加勒比海的猪兄弟Ⅱ——鬼影幢幢!亡灵岛的暗影城堡

题目背景

经过数日的航行,海盗船终于抵达了亡灵岛。

天色昏暗,浓雾弥漫,海风夹带着腐朽的气息,仿佛每一寸空气都充满了阴冷与危险。猪大和猪二站在船头,望着远方那座阴森的岛屿。岛屿周围被一片黑暗森林所环绕,古老的树木枝繁叶茂,树干扭曲如同鬼影重重,每一棵都像是一个个张牙舞爪的恶魔。

小猪们迅速跳下船,踏上这片诡异的土地。“到了,三弟就在这岛上,这片森林被称为死亡森林,我们得格外小心。”猪大语气严肃。“是啊,岛上看起来阴森恐怖,真不知道会有什么等着我们。”猪二也不禁打了个寒战。猪大咬紧牙关:“别怕,三弟就在前方,我们一定要把他救出来!”

小猪们每一步踩在湿滑的泥土上,都发出令人毛骨悚然的回声。周围的树林静得出奇,仿佛连风都不敢在这里流动。树木间的阴影愈发深重,光线被遮挡得几乎全无。树枝缠绕在一起,仿佛无形的锁链,把他们的前行一步步阻隔。猪二一边警惕地四下打量,一边低声说道:“这森林太诡异了,我们得加快脚步。”

走了好一会儿,树林终于开始稀疏,前方豁然开朗,一座巍峨的城堡出现在眼前。城堡古老且阴森,仿佛沉睡了几个世纪,墙壁上爬满了藤蔓,绿色的藤蔓如同触手一般缠绕着城堡的每一寸墙面。城堡的窗户深邃而幽暗,从中透出诡异的绿光,像一双双鬼魅般的眼睛,紧紧盯着他们,令人不寒而栗。

图像由ChatGPT生成

猪二忍不住打了个寒战:“这地方看起来不太对劲,难道三弟就被关在里面?”猪大的眼中闪过一丝坚定:“不管前方多么危险,三弟就在这座暗影城堡里面,我们不能退缩。”它们走近城堡的大门,发现门被厚重的石块堵住,完全无法推开。猪二急忙伸手去摸石门的缝隙,试图找到突破口:“怎么打开这个门?”

就在这时,猪大突然注意到大门旁边有一个奇怪的石头阵,阵法复杂而古老,石头排列成一圈,中央有一个凹陷的槽口,看上去像是某种机关。猪二走过去,蹲下身仔细打量:“这是什么东西?看起来像是一个谜题。”猪大也蹲下,仔细观察周围的石头阵:“这石头阵需要用水来激活。看这里的槽口,好像需要水才能启动这个机关,可能是用来打开大门的。”

题目描述

石头阵的槽口呈线性条带形,从左到右编号依次为00101810^{18}。所有槽口在初始时均为干燥。

你可以执行以下操作:选择两个空槽口iijj,使得iji\ne jijk\vert i-j\vert \le k,并将槽口iijj浇水。

给定序列aa,该序列中的所有槽口必须都被浇水,最多只能一个不在此序列中的槽口被浇水。你的任务是帮小猪兄弟确定使这一切成为可能的最小值kk

题目格式

题目输入

第一行包含一个整数T(1T103)T(1\le T\le 10^3),代表测试样例组数。对于每组测试用例:

  • 第一行包含一个整数n(1n2×103)n(1\le n\le 2\times 10^3)
  • 第二行包含nn个整数$a_1,a_2,\cdots,a_n(0\le a_i\le 10^{18},a_i<a_{i+1})$。

题目保证所有测试用例中n2×103\sum n\le 2\times 10^3

题目输出

对于每个测试用例,输出一个整数kk,表示所有给定单元被浇水的最小值。

题目样例

4
2
1 2
1
7
3
2 4 9
5
1 5 8 10 13
1
1
2
3

样例解释

  • 在第一个样例中,使用k=1k = 1,可以浇上槽口(1,2)(1,2)
  • 在第二个样例中,使用k=1k = 1,可以浇上槽口(7,8)(7,8)
  • 在第三个样例中,使用k=2k = 2,可以浇上槽口(2,4)(2,4)(8,9)(8,9)
  • 在第四个样例中,使用k=3k = 3,可以浇上槽口(0,1),(5,8),(10,13)(0,1),(5,8),(10,13)

系列简介

《加勒比海的猪兄弟》是由@主编的一部短篇冒险小说,故事讲述了在加勒比海的波涛之间,勇敢的海盗猪三兄弟展开了一段充满奇遇与挑战的冒险旅程。在骷髅海的军团袭击、亡灵岛的神秘城堡与肥猪黑心实验厂的险象环生中,他们齐心协力,克服了种种危险。在历尽艰难险阻后,三兄弟终于找到了属于自己的平静与幸福。本小说共4章,环环相扣,引人入胜。

本系列题目: