推荐题目：洛谷 P3641 [APIO2016] 最大差分

推荐题目洛谷P3641 [APIO2016] 最大差分题目背景评测方式以下是本题评测方式与题面不符时以这里为准。你的代码中不应该包含gap.h库。你的代码中需如下进行findGap和MinMax函数的声明externCvoidMinMax(longlong,longlong,longlong*,longlong*);externClonglongfindGap(int,int);spj 与交互库不保证没锅要是有锅请私信供题人然后 D 死他。题目描述有N NN个严格递增的非负整数a 1 , a 2 , … , a N a_1, a_2, \dots, a_Na1​,a2​,…,aN​0 ≤ a 1 a 2 ⋯ a N ≤ 10 18 0 \leq a_1 a_2 \cdots a_N \leq 10^{18}0≤a1​a2​⋯aN​≤1018。你需要找出a i 1 − a i a_{i 1} - a_iai1​−ai​1 ≤ i ≤ N − 1 1 \leq i \leq N - 11≤i≤N−1里的最大的值。你的程序不能直接读入这个整数序列但是你可以通过给定的函数来查询该序列的信息。关于查询函数的细节请根据你所使用的语言参考下面的实现细节部分。你需要实现一个函数,该函数返回a i 1 − a i a_{i 1} - a_iai1​−ai​1 ≤ i ≤ N − 1 1 \leq i \leq N - 11≤i≤N−1中的最大值。实现细节本题只支持 C包括 cpp11cpp14cpp17。C/C你需要包含头文件gap.h。你需要实现一个函数findGap(T, N)该函数接受下面的参数并返回一个long long类型的整数T TT子任务的编号1 11或者2 22N NN序列的长度你的函数findGap可以调用系统提供的查询函数MinMax(s, t, mn, mx)该函数的前两个参数s ss和t tt是long long类型的整数后两个参数mn和mx是long long类型的整数的指针mn和mx是long long类型的整数。当MinMax(s, t, mn, mx)返回时变量mn将会存储满足a i ∈ [ s , t ] a_i \in [s, t]ai​∈[s,t]中a i a_iai​的最小值变量mx将会存储满足a i ∈ [ s , t ] a_i \in [s, t]ai​∈[s,t]a i a_iai​的最大值。如果区间[ s , t ] [s, t][s,t]中没有序列中的数则mn和mx都将存储− 1 -1−1。在查询时需要满足s ≤ t s \leq ts≤t否则程序将会终止该测试点计为0 00分。Pascal你需要使用单元graderhelperlib。你需要实现一个函数findGap(T, N)该函数接受下面的参数并返回一个Int64类型的整数T TT子任务的编号1 11或者2 22Integer类型N NN序列的长度LongInt类型你的函数findGap可以调用系统提供的查询函数MinMax(s, t, mn, mx)该函数的前两个参数s ss和t tt是Int64类型的整数后两个参数mn和mx是传引用方式的Int64类型的整数过程内部对这两个变量的修改会影响到外部的对应变量的值。当MinMax(s, t, mn, mx)执行完毕时变量mn将会存储满足a i ∈ [ s , t ] a_i \in [s, t]ai​∈[s,t]中a i a_iai​的最小值变量mx将会存储满足a i ∈ [ s , t ] a_i \in [s, t]ai​∈[s,t]a i a_iai​的最大值。如果区间[ s , t ] [s, t][s,t]中没有序列中的数则mn和mx都将存储− 1 -1−1。在查询时需要满足s ≤ t s \leq ts≤t否则程序将会终止该测试点计为0 00分。输入格式样例一C/C考虑N 4 , a 1 2 , a 2 3 , a 3 6 , a 4 8 N 4, a_1 2, a_2 3, a_3 6, a_4 8N4,a1​2,a2​3,a3​6,a4​8。则答案应该是3 33可以通过下面的几组对MinMax的询问获得调用MinMax(1, 2, mn, mx)则mn和mx皆返回2 22。调用MinMax(3, 7, mn, mx)则mn返回3 33mx返回6 66。调用MinMax(8, 9, mn, mx)则mn和mx皆返回8 88。Pascal考虑N 4 , a 1 2 , a 2 3 , a 3 6 , a 4 8 N 4, a_1 2, a_2 3, a_3 6, a_4 8N4,a1​2,a2​3,a3​6,a4​8。则答案应该是3 33可以通过下面的几组对MinMax的询问获得调用MinMax(1, 2, mn, mx)则mn和mx皆返回2 22。调用MinMax(3, 7, mn, mx)则mn返回3 33mx返回6 66。调用MinMax(8, 9, mn, mx)则mn和mx皆返回8 88。样例评测方式样例测评系统从标准输入中读入两行。第一行包含两个整数子任务编号T TT和序列长度N NN。第二行包含N NN个严格递增的非负整数。然后该程序会向标准输出中写入两行第一行为findGap的返回值第二行为花费M MM的值。下面的输入描述了上面的样例2 4 2 3 6 8注意实际使用的交互库和 spj 对数据进行了加密。输出格式无说明/提示限制与约定对于所有的测试点有2 ≤ N ≤ 100000 2 \leq N \leq 1000002≤N≤100000。每一个测试点开始测试之前M MM都将被初始化为0 00。子任务 130 3030分每一次调用MinMax都将使M MM加1 11。为了获得所有分数需要满足对于该子任务下的所有测试点都有M ≤ N 1 2 M \leq \frac{N 1}{2}M≤2N1​。子任务 270 7070分定义k kk为调用MinMax时区间[ s , t ] [s, t][s,t]中的序列中数的数量。每次调用MinMax将使M MM加上k 1 k 1k1。对于每一个测试点如果M ≤ 3 N M \leq 3NM≤3N你将得到 70 分否则将得到60 M N 1 − 1 \dfrac{60}{\sqrt{\frac MN 1} - 1}NM​1​−160​分。你的该子任务的得分是其下所有测试点中的最低分。