小苯的麦克斯【牛客tracker 每日一题】

小苯的麦克斯时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小苯在学习计算机的过程中接触到了两个概念M A X MAXMAX和M E X MEXMEX对于一个序列来说前者表示序列中的最大值后者表示序列中未出现的最小非负整数。这天小红给了小苯一个长度为n nn的序列她知道小苯分不清这些概念因此特意提出了一个结合两个概念的题目她希望小苯从a aa中选择一个连续区间不能只选一个数字l , r ( 1 ≤ l r ≤ n ) l,r (1≤lr≤n)l,r(1≤lr≤n)并最大化区间中所有的数字的M A X − M E X MAX−MEXMAX−MEX即最大值减去最小未出现非负整数的值。现在请你帮小苯回答一下这个问题吧。输入描述每个测试文件包含多组测试数据。第一行输入一个整数T ( 1 ≦ T ≦ 10 4 ) T (1≦T≦10^4)T(1≦T≦104)代表数据组数每组测试数据描述如下第一行一个正整数n ( 2 ≦ n ≦ 3 × 10 5 ) n (2≦n≦3×10^5)n(2≦n≦3×105)表示序列a aa的长度。第二行n nn个整数a i ( 0 ≦ a i ≦ 10 9 ) a_i (0≦a_i≦10^9)ai​(0≦ai​≦109)表示序列a aa。除此之外保证所有测试数据中n nn的总和不超过3 × 10 5 3×10^53×105。输出描述对于每组数据在单独的一行输出一个整数表示题目所求的最大值。示例1输入2 5 1 2 3 4 5 4 0 0 0 0输出5 -1说明对于第一组测试数据选择区间[ 1 , 5 ] [1,5][1,5]即可此时最大值为5 55而最小未出现非负整数为0 00因此M A X − M E X 5 − 0 5 MAX−MEX5−05MAX−MEX5−05。对于第二组测试数据选择区间[ 1 , 4 ] [1,4][1,4]即可此时最大值为0 00而最小未出现非负整数为1 11此时M A X − M E X 0 − 1 − 1 MAX−MEX0−1−1MAX−MEX0−1−1。解题思路本题核心是贪心结论线性枚举求解最优值彻底规避暴力枚举的高复杂度。通过数学推导可证明满足条件的最优连续区间一定是长度为2的相邻元素对更长的区间无法得到比二元区间更优的结果。因此只需遍历数组中所有相邻的两个元素分别计算每对元素的区间最大值M A X MAXMAX和最小未出现非负整数M E X MEXMEX求二者差值并维护全局最大值。该方法将时间复杂度优化至线性O ( n ) O(n)O(n)完美适配多组测试数据、总长度不超过3 × 10 5 3 \times 10^53×105的大数据规模高效且精准。总结核心逻辑最优解仅存在于相邻两个元素的区间内直接枚举所有二元组即可得到答案。关键操作线性遍历数组相邻元素逐组计算M A X − M E X MAX-MEXMAX−MEX并更新最大值。效率保障线性时间复杂度无冗余计算完美满足题目时间与数据规模要求。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e410;constll p1e97;constll INF1e18;constll M5e310;intmain(){ll t;cint;while(t--){ll n;cinn;vectorlla(n);for(ll i0;in;i)cina[i];ll sum-1;for(ll i1;in;i){ll s00,s10;ll mmax(a[i],a[i-1]);if(a[i]0||a[i-1]0)s01;if(a[i]1||a[i-1]1)s11;if(s0){if(s1)mm-2;elsemm-1;}summax(sum,m);}coutsumendl;}return0;}