做外贸的网站有哪些,做接口的网站,建设网站的公司兴田德润实力强,asp.net 登陆两个网站这题我们是怎么思考的呢#xff1f;
已知有乘客最多30000个#xff0c;有最多100000个地点#xff0c;那么通过算法时间复杂度#xff0c;不可能是O(n^2),
那么我们就可以去看题目#xff0c;题目又是最多盈利多少元#xff1f;那么很容易联想到动态规划#xff0c;并… 这题我们是怎么思考的呢
已知有乘客最多30000个有最多100000个地点那么通过算法时间复杂度不可能是O(n^2),
那么我们就可以去看题目题目又是最多盈利多少元那么很容易联想到动态规划并且我们又发现该数组排个序之后可以让其递归时某个状态呈现出递推性质那么我们就确定是动态规划算法了 那么在确定是动态规划算法之后的话我们该去怎么分析呢是根据我们的经验去定义吗
那么我们就以f[i]表示以当前i为下车点的最大值那么这样去定义可以吗其实是不太行的因
为以当前i为结尾的话我们必须记录第i个为下车点的时候值如果没有那么就得是f[i] 0那么这样就比较麻烦其实应该也是可以做的只是这样做很麻烦。
那么我们试想以下这样去定义f[i]表示在1~i之内接到的乘客的最大利润那么我们发现
f[i - 1]表示在1 ~ i - 1之内接到的乘客的最大利润。 枚举乘客
假设当前乘客是a小于a上车点并且
b下车点 a上车点的乘客集合记作b 那么f[a下车点]要保证是最大的话那么需要知道是否要接上a这个乘客
如果要接上该乘客的话 那么我们要保证f[a下车点]是最大的 那么就需要找到小于a上车点的最大利润的状态又分为两种状态 1.第一种a乘客一定可以上车 那么f[a下车点] max({f[b集合的下车点]b E 1 ~ a上车点}) 当前乘客的利润 2.第二种a乘客一定不能上车 那么就需要找到小于a上车点的最大利润的状态 那么f[a下车点] max({f[b集合的下车点]b E 1 ~ a上车点}) 那么总结下来就是枚举当前看前面
那么我们怎么枚举呢
按照每个乘客的上车起点升序进行枚举。为什么呢 那么枚举当前怎么确保前面的值是最大的呢用一个堆来维护小于当前st的最大利润
那么该什么时候入堆什么时候出堆呢
比如第一个乘客st是1ed是5
第二个乘客是st是2ed是5
第三个乘客是st是3ed是7
我们发现该组数据中我们的车只能接三个乘客的一种所以当st小于下车点的时候
直接入堆即可当遇到st大于等于下车点话那么根据key(下车点)的堆进行判断找到
前面乘客最大下车点符合当前乘客st前面的乘客的最大下车点找到之后
就变成 1.第一种a乘客一定可以上车
如果没有那就 2.第二种a乘客一定不能上车 class Solution {
public:typedef pairlong long,long long PLL;struct CompareFirst {bool operator()(const PLL a, const PLL b) {return a.first b.first; // for a min heap, for a max heap}
};long long maxTaxiEarnings(int n, vectorvectorint rides) {vectorlong long f(n 10);//按照st大小排序sort(rides.begin(), rides.end(), [](const vectorint a, const vectorint b) - bool {return a[0] b[0];});int m rides.size();priority_queuePLL, vectorPLL, CompareFirst pq;long long res 0,maxv 0;for(int i 0;i m;i){long long st rides[i][0],ed rides[i][1],tip rides[i][2];while(!pq.empty() pq.top().first st)//如果队头的下车时间小于当前的st那么进行判断{//判断什么呢找到比当前st小的最大值maxv max(maxv,pq.top().second);pq.pop();}//找到之后计算出加上当前乘客的利润long long curv maxv ed - st tip;//加上之后入堆res max(res,curv);pq.push({ed,curv});}return res;}
};
