本文主要是介绍积压订单中的订单总数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
原题指路
积压订单中的订单总数
题目描述
给你一个二维整数数组 orders
,其中每个 orders[i] = [pricei, amounti, orderTypei]
表示有 amounti
笔类型为 orderTypei
、价格为 pricei
的订单。
订单类型 orderTypei
可以分为两种:
0
表示这是一批采购订单buy
1
表示这是一批销售订单sell
注意,orders[i]
表示一批共计 amounti
笔的独立订单,这些订单的价格和类型相同。对于所有有效的 i
,由 orders[i]
表示的所有订单提交时间均早于 orders[i+1]
表示的所有订单。
存在由未执行订单组成的 积压订单 。积压订单最初是空的。提交订单时,会发生以下情况:
- 如果该订单是一笔采购订单
buy
,则可以查看积压订单中价格 最低 的销售订单sell
。如果该销售订单sell
的价格 低于或等于 当前采购订单buy
的价格,则匹配并执行这两笔订单,并将销售订单sell
从积压订单中删除。否则,采购订单buy
将会添加到积压订单中。 - 反之亦然,如果该订单是一笔销售订单
sell
,则可以查看积压订单中价格 最高 的采购订单buy
。如果该采购订单buy
的价格 高于或等于 当前销售订单sell
的价格,则匹配并执行这两笔订单,并将采购订单buy
从积压订单中删除。否则,销售订单sell
将会添加到积压订单中。
输入所有订单后,返回积压订单中的 订单总数 。由于数字可能很大,所以需要返回对1e9 + 7
取余的结果。
解题思路
这道题的关键在于如何快速地匹配到销售订单的最小值以及采购订单的最大值。于是,我……毫不犹豫地调用了STL中的优先队列来维护这一最小值与最大值序列。
代码
struct order//先定义一个order结构体,指定两类订单不同的排序顺序
{int price, amount, type;friend bool operator< (order n1, order n2){if(n1.type == 0)return n1.price < n2.price;elsereturn n1.price > n2.price;}
};class Solution
{public:priority_queue<order> buy;priority_queue<order> sell;int getNumberOfBacklogOrders(vector<vector<int>>& orders) {int mod = 1e9 +7;for(int i = 0; i < orders.size(); i++)//主要过程就是在插入同时不断去维护这两个优先队列if(orders[i][2] == 0){while(!sell.empty() && sell.top().price <= orders[i][0]){if(sell.top().amount < orders[i][1]){orders[i][1] -= sell.top().amount;sell.pop();}else if(sell.top().amount == orders[i][1]){sell.pop();orders[i][1] = 0;break;}else if(sell.top().amount > orders[i][1]){order temp = sell.top();sell.pop();temp.amount -= orders[i][1];sell.push(temp);orders[i][1] = 0;break;}}if(orders[i][1])buy.push({orders[i][0], orders[i][1], orders[i][2]});}else{while(!buy.empty() && buy.top().price >= orders[i][0]){if(buy.top().amount < orders[i][1]){orders[i][1] -= buy.top().amount;buy.pop();}else if(buy.top().amount == orders[i][1]){buy.pop();orders[i][1] = 0;break;}else if(buy.top().amount > orders[i][1]){order temp = buy.top();buy.pop();temp.amount -= orders[i][1];buy.push(temp);orders[i][1] = 0;break;}}if(orders[i][1])sell.push({orders[i][0], orders[i][1], orders[i][2]});}int sum = 0;while(!sell.empty()){sum = (sum + sell.top().amount % mod) % mod;sell.pop();}while(!buy.empty()){sum = (sum + buy.top().amount % mod) % mod;buy.pop();}return sum;}
};
这篇关于积压订单中的订单总数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!