阿里 4.10 笔试

第一道，2d地图上有n座房子，给的输入数据是n座房子的x，y坐标，现在要修一条水渠，水渠平行于y轴无限长，问每座房子到该水渠的距离之和最小是多少？
第二题是染色问题，给定一个矩阵的size，颜料有c种，每种颜料的量给定，每涂一个格子消耗颜料一升。请问是否能找到染色方案，使得相邻的格子的颜色不同。返回true or false。

第二题 我没做出来，但感觉是bfs可以解决，颜料和对应的剩余量用字典存，相邻的格子有边相连，从（0，0）开始，同一层的节点涂同个颜色，涂下一层节点选择剩余最多的且不同于上一层的颜料。若发现某一层，找不到符合条件的颜料那么return false。如果遍历完整个图，那么return true

第一题应该就是median


第二题
思路大概是


黑白黑白黑白
白黑白黑白黑
黑白黑白黑白
白黑白黑白黑

对角线然后最多的那个颜色填黑 如果某种颜色太多了那就填不下

感觉好难，一题都没做出来，求问第一题怎么做？

菜哭了，第一题不是求中位数吗？我一直没ac。。第二题都没时间写。我看牛客上有说用鸽巢原理的，只需要判断是否有一种颜色超过半数就可以判断能否填满