https://leetcode-cn.com/problems/campus-bikes/
class Solution {
public:
vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
map<int, vector<pair<int, int> > > distance;
//每一个曼哈顿距离的工人-自行车对
int w[1005] = {0};
int b[1005] = {0};
vector<int> ans(workers.size());
/* 两重循环遍历所有可能,因为循环索引是从小到大的,
自然符合优先选择索引小的
*/
for (int i = 0; i < workers.size(); ++i) {
for (int j = 0; j < bikes.size(); ++j) {
int dis = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]);
distance[dis].push_back({i, j});
}
}
for (auto &m : distance) {
for (auto &p : m.second) {
if (w[p.first] || b[p.second])
continue;
ans[p.first] = p.second;
w[p.first] = b[p.second] = 1;
}
}
return ans;
}
};