招行信用卡M-Geeker竞赛部分题解+讨论
趁热。。
第一题(100%): 水题,但题意看了几分钟才看懂
第二题(60%): 在一个矩阵中找两个不在同一行也不在同一列的数,使乘积最大。
解法:用map存每个数存在的位置,map的key 降序排列。然后遍历矩阵,矩阵的每个位置ai,j 都找第一个满足条件的map(设为mp_i,j),求ai,j * mp_i,j的最大值
第三题(100%): 小明要在t分钟之内做l张饼,有n个锅,但只能选其中k个锅,每个锅每分钟能做vi个饼,最多能做mi个饼,问能不能做完l张饼,如果能,输出最少需要多少分钟;如果不能,输出最多能做几张饼。
解法: 先讨论能不能做完:每个锅在t分钟内能做的饼数为min(mi,vi*t), 降序排列,前k个锅能做出来的饼>l就能; 如果不能做完:直接输出前k个锅能做饼的和;如果能:二分最短时间,然后判断在mid分钟内能不能做完饼,判断方法同t分钟的情况
第四题(100%): 给定一个序列,可以删除其任意长度的连续子串,求剩下的序列的最大子段和。
解法:其实就是求序列中两个不相交的区间的最大和。从左往右扫一遍求0<=index<=i的最大子段和,记为seq[i];再从右往左一遍,求 n>index>=i的最大子段和,记为rseq[i];最后从左往右扫一遍,求max(seq[i]+rseq[i+1])。
第五题(0%): 不会
第六题(30%): 3种操作,1 L R V: 在区间【L,R】上增加任务V; 2 L R V: 在区间[L,R]上删除任务V ; 0 L R : 查询区间[L,R] 上的任务数。
解法: 感觉是某种高级数据结构,形式上像线段树,不过我忘得差不多了,不会做,暴力一发30%。求大佬解答!