阿里研发岗 0530笔试真题-矩阵两次取线最大收益(详细思路+多语言题解)

矩阵两次取线最大收益阿里研发岗 0530笔试 第二题题目内容给定一个n×mn \times mn×m的整数矩阵AAA。你需要进行两次操作每次选择一行或一列将所选行或列上的所有元素取走并累加到总和中。被取走后该行或该列上所有被选择到的元素的值立即变为000在后续操作中按000计。求能够获得的最大总和。更形式化地设两次操作依次选择的线为L1,L2L_1, L_2L1​,L2​。第一次操作的收益为L1L_1L1​上元素之和将L1L_1L1​上元素全部置为000后第二次操作的收益为此时L2L_2L2​上元素之和答案为两次收益之和。输入描述输入包含多组测试数据。第一行包含整数T (1≤T≤105)T\ (1 \le T \le 10^5)T(1≤T≤105)表示测试组数。每组数据描述如下第一行包含两个整数n,m (1≤n,m, n×m≤2×105)n, m\ (1 \le n, m,\ n \times m \le 2 \times 10^5)n,m(1≤n,m,n×m≤2×105)接下来nnn行每行包含mmm个整数表示矩阵 A 的元素Ai,j (−109≤Ai,j≤109)A_{i,j}\ (-10^9 \le A_{i,j} \le 10^9)Ai,j​(−109≤Ai,j​≤109)。保证所有测试中n×mn \times mn×m的总和不超过5×1055 \times 10^55×105。输出描述对于每组测试数据输出一行一个整数表示进行两次操作可以获得的最大总和。样例1输入3 3 3 1 2 3 4 5 6 7 8 9 2 3 -1 10 -3 10 1 5 1 4 5 -1 4 -2输出39 26 9说明样例一选择第222行与第333行总和为15243915 24 39152439为最优。样例二第一次选择第222行收益为10151610 1 5 16101516将该行置零后再选择第222列此时该列仅剩(1,2)(1,2)(1,2)位置的101010收益101010。合计16102616 10 26161026。样例三仅选择第一列和第三列总和为5495 4 9549。题解思路逻辑分析取两条线只会存在三种类型方案取一行和一列取两行取两列依次确定上面三种类型所能取到的最大值就是结果定义maxValue记录最大值。对于行、列总和计算可预处理使用rowSum和colSum求和复用。不同方案处理取一行 一列会存在a[i][j]重叠计算两次需要减去一次枚举行 列的组合对应行和列的和为rowSum[i] colSum[j] - a[i][j]取两行/两列不会产生重叠直接对rowSum和colSum进行排序分别取rowSum和colSum两个最大值相加即可得知。3、4计算中最大值就是结果。C#includebits/stdc.husingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intn,m;cinnm;// 行总和 列总和vectorlongrowSum(n,0),colSum(m,0);vectorvectorlonga(n,vectorlong(m));for(inti0;in;i){for(intj0;jm;j){cina[i][j];rowSum[i]a[i][j];colSum[j]a[i][j];}}longmaxValueLONG_MIN;// 枚举选取行 列for(inti0;in;i){for(intj0;jm;j){maxValuemax(maxValue,rowSum[i]colSum[j]-a[i][j]);}}sort(colSum.begin(),colSum.end());sort(rowSum.begin(),rowSum.end());if(m2){maxValuemax(maxValue,colSum[m-1]colSum[m-2]);}if(n2){maxValuemax(maxValue,rowSum[n-1]rowSum[n-2]);}coutmaxValueendl;}return0;}javaimportjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intTsc.nextInt();while(T--0){intnsc.nextInt();intmsc.nextInt();// 行总和 列总和long[]rowSumnewlong[n];long[]colSumnewlong[m];long[][]anewlong[n][m];for(inti0;in;i){for(intj0;jm;j){a[i][j]sc.nextLong();rowSum[i]a[i][j];colSum[j]a[i][j];}}longmaxValueLong.MIN_VALUE;// 枚举选取行 列for(inti0;in;i){for(intj0;jm;j){maxValueMath.max(maxValue,rowSum[i]colSum[j]-a[i][j]);}}Arrays.sort(colSum);Arrays.sort(rowSum);if(m2){maxValueMath.max(maxValue,colSum[m-1]colSum[m-2]);}if(n2){maxValueMath.max(maxValue,rowSum[n-1]rowSum[n-2]);}System.out.println(maxValue);}}}pythontint(input())for_inrange(t):n,mmap(int,input().split())# 行总和 列总和row_sum[0]*n col_sum[0]*m a[[0]*mfor_inrange(n)]foriinrange(n):a[i]list(map(int,input().split()))forjinrange(m):row_sum[i]a[i][j]col_sum[j]a[i][j]max_value-float(inf)# 枚举选取行 列foriinrange(n):forjinrange(m):max_valuemax(max_value,row_sum[i]col_sum[j]-a[i][j])row_sum.sort()col_sum.sort()ifm2:max_valuemax(max_value,col_sum[-1]col_sum[-2])ifn2:max_valuemax(max_value,row_sum[-1]row_sum[-2])print(max_value)javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constinput[];rl.on(line,line{input.push(...line.trim().split(/\s/).map(Number));});rl.on(close,(){letidx0;letTinput[idx];while(T--){constninput[idx];constminput[idx];// 行总和 列总和constrowSumnewArray(n).fill(0);constcolSumnewArray(m).fill(0);constaArray.from({length:n},()newArray(m));for(leti0;in;i){for(letj0;jm;j){a[i][j]input[idx];rowSum[i]a[i][j];colSum[j]a[i][j];}}letmaxValue-Infinity;// 枚举选取行 列for(leti0;in;i){for(letj0;jm;j){maxValueMath.max(maxValue,rowSum[i]colSum[j]-a[i][j]);}}rowSum.sort((a,b)a-b);colSum.sort((a,b)a-b);if(m2){maxValueMath.max(maxValue,colSum[m-1]colSum[m-2]);}if(n2){maxValueMath.max(maxValue,rowSum[n-1]rowSum[n-2]);}console.log(maxValue);}});Gopackagemainimport(bufiofmtossort)funcmain(){in:bufio.NewReader(os.Stdin)varTintfmt.Fscan(in,T)for;T0;T--{varn,mintfmt.Fscan(in,n,m)// 行总和 列总和rowSum:make([]int64,n)colSum:make([]int64,m)a:make([][]int64,n)fori:0;in;i{a[i]make([]int64,m)forj:0;jm;j{fmt.Fscan(in,a[i][j])rowSum[i]a[i][j]colSum[j]a[i][j]}}varmaxValueint64-(162)// 枚举选取行 列fori:0;in;i{forj:0;jm;j{maxValuemax(maxValue,rowSum[i]colSum[j]-a[i][j],)}}sort.Slice(rowSum,func(i,jint)bool{returnrowSum[i]rowSum[j]})sort.Slice(colSum,func(i,jint)bool{returncolSum[i]colSum[j]})ifm2{maxValuemax(maxValue,colSum[m-1]colSum[m-2],)}ifn2{maxValuemax(maxValue,rowSum[n-1]rowSum[n-2],)}fmt.Println(maxValue)}}funcmax(a,bint64)int64{ifab{returna}returnb}