0821美团笔试

题目是n个长方形，我用go写的，一开始超时后改用hash缓存后还超时，真一点没招了，牛友们有遇到相同情况吗这是我的代码:package mainimport "fmt"func niceput(rectangles [][]int, height int) int {var ans intfor _, rectangle := range rectangles {if rectangle[0] <= height && rectangle[1] <= height {ans += min(rectangle[0], rectangle[1])} else {if rectangle[0] > height {ans += rectangle[0]} else {ans += rectangle[1]}}}return ans}func min(a, b int) int {if a <= b {return a}return b}func main() {firstmap := make(map[int]map[int]int)var n, m intfmt.Scan(&n, &m)ans := 0for i := 0; i < n; i++ {recs := [][]int{}var x, y intfmt.Scan(&x, &y)if x < y {x, y = y, x}//如果map中有结果，直接调用，不用再计算一次if v, ok := firstmap[x][y]; ok {ans += vcontinue}recs = append(recs, []int{x, y})curput := niceput(recs, m)ans += curputif _, ok := firstmap[x]; !ok {firstmap[x] = make(map[int]int)}firstmap[x][y] = curput//把结果记录在map中}fmt.Println(ans)}

深信服是不是还没开始筛简历啊，一直都显示申请成功，8月20投的，也没有下一步了

不得不说题目真的有点难了第二题：贪心，开两个multiset，分别存A和B，每次取出A和B最大的，如果A的最大值大于B最大值，A最大值丢弃并将原最大值执行操作丢回set，计数+1；如果B最大值大于A最大值，B最大值丢弃并将原最大值执行操作丢回set，计数+1；如果相等，则分别丢弃最大值，计数值不变。最后输出计数值第三题：线段树可以做，但是很麻烦。有点类似于线段树求逆序对或线段树求最长上升子序列，需要维护对于某个i，在此前遍历的j>i有多少个比i大或小。首先复制一份排序后的数组，从后往前遍历，每个位置j，把所有右边比它大的顺序（k>j，且idx(a[k])>idx(a[j])）的idx(a[k])(idx(x)表示数组排序后，x所在位置)都+1（参考线段树区间逐元素加一个值的维护方式，带染色标记）。这里要注意的是，比某个数大的，在右边未必出现过，所以未出现的地方一开始要用负无穷初始化，出现后才置为整数，然后在线段树递归更新查询的时候维护一个判断条件，为正数才累计求和。这样，遍历到i的时候，可以算出i到k之间，有多少个j产生了贡献，然后把所有k的值求和，就可以了。

字符串模拟很简单，直接秒了。后面一道数学期望题，一道树题。还是太折磨了，期望题看样例就看了十分钟，还没骗到分。。。树题倒是硬跑暴力，拿了点保底