波动贡献最大化百度技术岗 笔试真题 8月6号 第一题题目内容运维侧拿到一条长度为n nn的整型指标序列v 1 , v 2 , … , v n v_1,v_2,\dots,v_nv1​,v2​,…,vn​需要按连续子段做汇总评估。要求子段非空、首尾相接且覆盖整条序列并使所有子段的「波动贡献」之和尽量大。对子段v L , v L 1 , … , v R v_L,v_{L1},\dots,v_RvL​,vL1​,…,vR​其长度为w ( L , R ) R − L 1 w(L,R)R-L1w(L,R)R−L1波动贡献定义为H ( L , R ) ( max ⁡ ( v L , v L 1 , … , v R ) − min ⁡ ( v L , v L 1 , … , v R ) ) × w ( L , R ) H(L,R)\bigl(\max(v_L,v_{L1},\ldots,v_R)-\min(v_L,v_{L1},\ldots,v_R)\bigr)\times w(L,R)H(L,R)(max(vL​,vL1​,…,vR​)−min(vL​,vL1​,…,vR​))×w(L,R)请给出可达到的最大总和。输入描述首先一行序列长度n nn( 1 ≤ n ≤ 3 × 10 5 ) (1 \le n \le 3\times 10^5)(1≤n≤3×105)。随后一行n nn个整型值构成的列表v 1 , v 2 , … , v n v_1,v_2,\dots,v_nv1​,v2​,…,vn​( 1 ≤ v i ≤ 10 9 ) (1 \le v_i \le 10^9)(1≤vi​≤109)。输出描述写出一个非负整型结果表示该序列划分下能得到的最大总价值。样例1输入3 2 5 1输出12说明将整段[ 2 , 5 , 1 ] [2,5,1][2,5,1]作为一个子段长度为3 33最大值为5 55最小值为1 11波动贡献为( 5 − 1 ) × 3 12 (5-1)\times 312(5−1)×312即为最优总价值。样例2输入4 1 5 2 4输出16说明将整段[ 1 , 5 , 2 , 4 ] [1,5,2,4][1,5,2,4]作为一个子段长度为4 44最大值为5 55最小值为1 11波动贡献为( 5 − 1 ) × 4 16 (5-1)\times 416(5−1)×416即为最优总价值。题解和思路思路实现思路逻辑分析需要分析出把一个区间拆成多个区间后波动贡献之和一定不会超过整个区间直接作为一个子段的贡献。具体分析过程如下整个数组v1....vn,整体波段贡献为(max(v) - min(v)) * n假设进行拆分左半部分长度为x, 波动为r1左半部分长度为y, 波动为r2整体长度为x y波动为r容易分析出r r1 and r r2r * (x y) r1x r2y所以只需要遍历找出输入数组最大值、最小值然后计算整体波动贡献即可。代码时间复杂度为OnC#includebits/stdc.husingnamespacestd;usinglllonglong;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;cinn;ll mnLLONG_MAX;ll mxLLONG_MIN;for(inti0;in;i){ll x;cinx;mnmin(mn,x);mxmax(mx,x);}cout(mx-mn)*n\n;return0;}Javaimportjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));intnInteger.parseInt(br.readLine().trim());longmnLong.MAX_VALUE;longmxLong.MIN_VALUE;String[]numsbr.readLine().trim().split( );for(inti0;in;i){longxLong.parseLong(nums[i]);mnMath.min(mn,x);mxMath.max(mx,x);}System.out.println((mx-mn)*n);}}pythonnint(input())mnfloat(inf)mxfloat(-inf)numslist(map(int,input().split()))forxinnums:mnmin(mn,x)mxmax(mx,x)print((mx-mn)*n)Javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constinput[];rl.on(line,line{input.push(line.trim());});rl.on(close,(){letindex0;constnNumber(input[index]);letmnNumber.MAX_SAFE_INTEGER;letmxNumber.MIN_SAFE_INTEGER;constnumsinput[index].split( ).map(Number);for(leti0;in;i){constxnums[i];mnMath.min(mn,x);mxMath.max(mx,x);}console.log((mx-mn)*n);});Gopackagemainimport(bufiofmtos)funcmain(){in:bufio.NewReader(os.Stdin)out:bufio.NewWriter(os.Stdout)deferout.Flush()varnintfmt.Fscan(in,n)varmnint64163-1varmxint64-163fori:0;in;i{varxint64fmt.Fscan(in,x)ifxmn{mnx}ifxmx{mxx}}fmt.Fprintln(out,(mx-mn)*int64(n))}