题解 | #旅行Ⅰ#

题目描述
牛妹出去旅行啦，她准备去N个城市旅行，去每个城市的开销是Ai元。但是牛妹有强迫症，她想在去y城市之前先旅游x城市，于是牛妹列出了这些限制条件list。并且牛妹很节约，她只有V元，她每次会选择当前能去的花费最小的城市,如有多个花费一样的则首先去编号小的城市，她想知道她最多能到多少个城市去旅游。

方法一：暴力解法

求解思路
对于求解本题牛妹最多能到多少个城市去旅游，我们可以直接模拟牛妹的访问过程，首先我们定义city，dp，flag数组，分别记录城市之间的次序关系，每个城市的前序访问和该城市有无被访问过。然后我们开始进行模拟访问，首先没有前序城市的城市进入队列，每次花费最小或者下标最小的城市出队，然后将相邻的后续城市的前序数量减一。最后我们可以遍历完所有城市，并且根据花费，计算出牛妹最多可以到达多少个城市去旅游。

解题代码

class Solution {
public:
     struct node
     {
        int val;
        int index;
        bool friend operator < (node a, node b) // 根据本题目重载小于号
        {   //花费优先，然后是下标
            if(a.val == b.val) 
                return a.index > b.index;
            return a.val > b.val;
        }
    };
    int Travel(int N, int V, vector<int>& A, vector<Point>& list)
    {
        vector<int> mydp(N + 1, 0); // 记录有多少个前序城市
        int res = 0; // 声明结果
        vector<vector<int> > city(N + 1, vector<int> ()); // 记录城市之间的次序
        for(int i = 0; i < list.size(); i++)
        {
            city[list[i].x].push_back(list[i].y); // 城市入队
            mydp[list[i].y]++; 
        }
        priority_queue<node> q;
        vector<bool> flag(N + 1, false); // 声明flag数组来记录该城市是否被访问
        for(int i = 1; i <= N; i++)
        {
            if(mydp[i] == 0)
            {
                q.push({A[i - 1], i}); // 没有前序的城市可以直接放入队列，优先访问花费最小的
                flag[i] = true; // 记录访问过该点
            }
        }
        while(!q.empty())
        {
            node temp = q.top();
            q.pop();
            if(temp.val > V) // 预算不够了
                break;
            V -= temp.val;
            res++;
            for(int i = 0; i < city[temp.index].size(); i++) // 该城市的所有后序城市的前序数量减一
                mydp[city[temp.index][i]]--;
            for(int i = 1; i <= N; i++)
            {   //遍历每个城市，如果该城市的前序为0且没有被访问过
                if(mydp[i] == 0 && !flag[i])
                {
                    q.push({A[i - 1], i});
                    flag[i] = true;
                }
            }
        }
        return res; // 返回结果
    }
};

复杂度分析
时间复杂度：两层循环加一个队列，因此时间复杂度为( )
空间复杂度：使用数组city[n][n],因此空间复杂度为( )

方法二：优化解法

求解思路
基于方法一，我们发现每次dp数组中的元素归零时，它一定还没有被访问过，同时它又只能收到前序城市的影响，因此我们可以将其直接加入队列中，从而省去flag数组，继而对代码进行优化。

解题代码

class Solution {
public:
     struct node
     {
        int val;
        int index;
        bool friend operator < (node a, node b) // 重载操作符<
        {   //花费优先，然后时下标
            if(a.val == b.val) 
                return a.index > b.index;
            return a.val > b.val;
        }
    };
    int Travel(int N, int V, vector<int>& A, vector<Point>& list)
    {
        vector<int> mydp(N + 1, 0); // 记录有多少个前序城市
        int myres = 0; // 记录结果
        vector<vector<int> > city(N + 1, vector<int> ()); //记录城市之间的次序
        for(int i = 0; i < list.size(); i++)
        {
            city[list[i].x].push_back(list[i].y); // 对城市进行判断
            mydp[list[i].y]++;
        }
        priority_queue<node> q;
        for(int i = 1; i <= N; i++)
            if(mydp[i] == 0)
                q.push({A[i - 1], i});
        while(!q.empty())
        {
            node temp = q.top();
            q.pop();
            if(temp.val > V) // 预算不够了
                break;
            V -= temp.val;
            myres++;
            for(int i = 0; i < city[temp.index].size(); i++)
            {   //该城市的所有后序城市的前序数量减一
                mydp[city[temp.index][i]]--;
                if(mydp[city[temp.index][i]] == 0) // 刚刚为0的城市一定还没有被访问过
                    q.push({A[city[temp.index][i] - 1], city[temp.index][i]});
            }
        }
        return myres; // 返回结果
    }
};

复杂度分析
时间复杂度：两层循环加一个队列，因此时间复杂度为( )，相比方法一省去了flag数组，使得运行结果的速度更快，并且占用的内存空间更少。
空间复杂度：使用数组city[n][n],因此空间复杂度为( )