Lọc Nhà Hàng Theo Thuận Tiện Cho Ăn Chay, Giá Và Khoảng Cách Trong C++

Giả sử mảng restaurants với restaurants[i] = [idi, ratingi, veganFriendly, pricei, distancei]. Lọc nhà hàng bằng ba bộ lọc:

• veganFriendly: true (chỉ lấy nhà hàng veganFriendly=1) hoặc false (lấy tất cả).

• maxPrice: giá tối đa.

• maxDistance: khoảng cách tối đa.

Trả về mảng ID nhà hàng sau lọc, sắp xếp theo rating giảm dần. Nếu rating bằng nhau, sắp xếp ID giảm dần. veganFriendly và vegan-friendly lấy giá trị 1 khi true, 0 khi false.

Ví dụ: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly=1, maxPrice=50, maxDistance=10 → [3,1,5].

Giải thích: Nhà hàng 1 [1,4,1,40,10], 2 [2,8,0,50,5], 3 [3,8,1,30,4], 4 [4,10,0,10,3], 5 [5,1,1,15,1]. Sau lọc veganFriendly=1, maxPrice=50, maxDistance=10 còn nhà hàng 3, 1, 5 (theo rating giảm).

Để giải quyết, chúng ta làm theo các bước:

• Tạo mảng temp, n = restaurants.size().

• Với i từ 0 đến n-1: nếu vf==0 hoặc r[i][2]==vf và r[i][3]<=mp và r[i][4]<=md: thêm [r[i][0], r[i][1]] vào temp.

• Sắp xếp temp giảm dần theo rating, nếu bằng nhau theo ID giảm dần.

• Tạo mảng ret, lấy ID từ temp.

• Trả về ret.

Ví dụ (C++)

Hãy xem triển khai sau để hiểu rõ hơn:

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}

class Solution {
public:
    static bool cmp(vector <int> a, vector <int> b){
        if(b[1] != a[1]) return a[1] > b[1];
        return a[0] > b[0];
    }
    vector<int> filterRestaurants(vector<vector<int>>& r, int vf, int mp, int md) {
        vector < vector <int> > temp;
        int n = r.size();
        for(int i = 0; i < n; i++){
            if((vf == 0 || r[i][2] == vf) && r[i][3] <= mp && r[i][4] <= md){
                temp.push_back({r[i][0], r[i][1]});
            }
        }
        sort(temp.begin(), temp.end(), cmp);
        vector <int> ret;
        for(int i = 0; i < temp.size(); i++) ret.push_back(temp[i][0]);
        return ret;
    }
};

int main(){
    vector<vector<int>> v = {{1,4,1,40,10},{2,8,0,50,5},{3,8,1,30,4},{4,10,0,10,3},{5,1,1,15,1}};
    Solution ob;
    print_vector(ob.filterRestaurants(v, 1, 50, 10));
}

Đầu vào

[[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]] 1 50 10

Đầu ra

[3,1,5]