高德地图 信息研发部 笔试

看评论区的各位大佬，我好悲伤

算了 我还是放弃算法吧

呃呃，，好难的样子

更新一下第二题思路： 1. 首先将所有的坐标转为一个三元组(x, y, num) 1. 这里要先剔除掉一些不符合的case：x<start>end 2. 依据end来给这一些三元组排序，放入一个最小堆中 3. 遍历[start,end],建立一个数组，dp[i]表示终点到i时能收获到最大利益，并存下收获最大利益情况下车上的剩余座位数，dp[i]={max_profit, res_num} profit()函数是计算收入的过程，这里省略具体计算公式 1. 假设第一个弹出的是(1,3,1)，则dp[3]={profit(1,3,1),2} 2. 假设第二个弹出的是(2,6,2)，则dp[6]取 max(max(dp[0]...dp[2])+profit(2,6,2),max(dp[3]...dp[5])), 注意，这里取dp的时候需要满足res_num>=num 3. 假设弹出的有多个，比如又弹了一个(1,6,1), 则再计算一遍max(max(dp[0]...dp[1])+profit(1,6,1),max(dp[2]...dp[5]))，取最大值 4. 总结来说，dp的设置方式如下： vector<pair><int>> dp; // 初始条件 dp[0]=0; // 设i点max_profit和res_num为dp[i] dp[i]={max_profit,res_num} // 下一个点终点为j点 (x_j,y_j,num_j) dp[j].max_profit=max( max(dp[0...x_j].max_profit if its res_num >= num_j), max(dp[x_j+1...y_j-1].max_profit) )</int></pair></start>

更新一下第三题思路：维护一个数组，这个数组代表第i家公司，再多接一个人需要额外花费多少。另外肯定还要维护一个cnt_i，记录第i家公司已经接了多少人了。然后每次就挑花费最小的出来，重复m次。假设第i家公司已经接了k个人，再多接1个人，新增的代价就是v_i * ((k+1)^2-k^2)，也就是v_i*(2k+1)。相当于贪心，每次都选一个开销最少的人上。时间复杂度m*lgn。

a了2道。第1道创建一个map，key是数组中的元素，value是这个元素出现的最小索引。[1，2，2，3，3，3，4]→map[1]=0，map[2] = 1，map3=3...然后排序map中的key值求第二大第二小。 第二题狠狠贪心。第三题看不懂，一点没写。